Id: palomar/PALOMAR-2026-11-16-000014 Url: https://github.com/hamsade-google/wowii-conjecture-19-lean/tree/949a857bfb20f75c38f57317c4e2c29e2c18aa1b Json: https://data.palomar-registry.org/entries/PALOMAR-2026-11-16-000014-v1.json Repo: https://github.com/hamsade-google/wowii-conjecture-19-lean Tags: math.CO, msc:05C12, msc:05C35, msc:05C69, msc:68V15 Score: 0 Title: Written on the Wall II Conjecture 19: lower bound on the largest induced bipartite subgraph size from average eccentricity and neighborhood independence Trust: high Domain: math.CO Source: palomar Authors: Hamed Sadeghi Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-16 Formalized: true Page: https://delphi.science/r/palomar/PALOMAR-2026-11-16-000014 Lean 4 / Mathlib formalization of Conjecture 19 from E. DeLaVina's Written on the Wall II (Graffiti.pc) collection, matching the exact statement in google-deepmind/formal-conjectures (WrittenOnTheWallII.GraphConjecture19.conjecture19). For every finite, nontrivial, connected simple graph G, the size b(G) of a largest induced bipartite subgraph is bounded below by the floor of the sum of the average vertex eccentricity and the maximum local neighborhood independence number sup_v l(v). The proof picks a vertex u maximising l(u), sets e = (G.eccent u).toNat and D = G.diam, and constructs an…