/- Copyright 2025 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Written on the Wall II - Conjecture 19

Reference: E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc

@[expose] public sectionnamespace WrittenOnTheWallII.GraphConjecture19open SimpleGraphvariable {α : Type*} [Fintype α] [DecidableEq α]

WOWII Conjecture 19

If $G$ is connected then the size $b(G)$ of a largest induced bipartite subgraph satisfies $b(G) \ge \left\lfloor \frac{\sum_v \mathrm{ecc}(v)}{|V|} + \sup_v l(v) \right\rfloor$, where $\mathrm{ecc}(v)$ denotes eccentricity and $l(v)$ is the independence number of the neighbourhood of $v$.

Proof outline. Pick $u$ maximising $l(u)$, let $e = \mathrm{ecc}(u)$ and $D = \mathrm{diam}(G)$, and let $I \subseteq N(u)$ be an independent set with $|I| = l(u)$. Any family of sets $B_d$, each independent and contained in the distance sphere ${v \mid \mathrm{dist}(u, v) = d}$, induces a bipartite subgraph (colour by the parity of $\mathrm{dist}(u, \cdot)$), so $b(G) \ge \sum_d |B_d|$.

    If $D \le e$, every eccentricity is at most $e$, so the average is at most $e$. Take $B_0 = {u}$, $B_1 = I$, and one vertex of a geodesic from $u$ to an eccentric vertex on each sphere $2 \le d \le e$; this gives $b(G) \ge e + l(u)$.

    If $e < D$, the average eccentricity is strictly less than $D$. Take a diametral pair $x, y$. On each sphere $d$ in a suitable range, the vertices of geodesics $u \to x$ and $u \to y$ at distance $d$ from $u$ are at distance at least $2$ from each other (triangle inequality with $\mathrm{dist}(x, y) = D$), so they can share $B_d$; counting gives $b(G) \ge D - 1 + l(u)$. In both cases the floor of the average plus $l(u)$ is at most $b(G)$.

@[category research solved, AMS 5, formal_proof using lean4 at "https://palomar-registry.org/entry.html?id=PALOMAR-2026-11-16-000014"] theorem conjecture19 (G : SimpleGraph α) [Nontrivial α] (h_conn : G.Connected) : ⌊(∑ v ∈ Finset.univ, ((G.eccent v).toNat : ℝ)) / (Fintype.card α : ℝ) + sSup (Set.range (indepNeighbors G))⌋ ≤ b G := α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:Nontrivial αh_conn:G.Connected⊢ ↑⌊(∑ v, ↑(G.eccent v).toNat) / ↑(Fintype.card α) + sSup (Set.range G.indepNeighbors)⌋ ≤ G.b All goals completed! 🐙end WrittenOnTheWallII.GraphConjecture19