Written on the Wall II - Conjecture 23

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

theorem WrittenOnTheWallII.GraphConjecture23.conjecture23 {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] : False ↔ ∀ (G : SimpleGraph α) [inst : DecidableRel G.Adj], G.Connected → have M := {v : α | G.degree v = G.maxDegree}; ↑⌊↑G.indepNum + G.distavg M / 2⌋ ≤ G.b

WOWII Conjecture 23

For a simple connected graph G, b(G) ≥ ⌊α(G) + dist_avg(M, V) / 2⌋, where b(G) is the size of a largest induced bipartite subgraph, α(G) is the independence number, and M is the set of maximum-degree vertices, and dist_avg(M, V) is the average distance from all vertices to M.

This conjecture is false; there is a counterexample with b(G) = 19, α(G) = 15, and dist_avg(M, V) = 10.