Written on the Wall II - Conjecture 17

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

theorem WrittenOnTheWallII.GraphConjecture17.conjecture17 {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) (h : G.Connected) : ↑G.indepNum + ↑⌈↑G.diam / 3⌉ ≤ G.b

WOWII Conjecture 17

For a simple connected graph G, the size b(G) of a largest induced bipartite subgraph satisfies b(G) ≥ α(G) + ⌈diam(G) / 3⌉, where α(G) is the independence number of G and diam(G) is the diameter of G.