Written on the Wall II - Conjecture 141

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

theorem WrittenOnTheWallII.GraphConjecture141.conjecture141 {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) (h : G.Connected) : G.girth / 2 - 1 + Finset.univ.sup G.indepNeighborsCard ≤ G.largestInducedTreeSize

WOWII Conjecture 141

For a simple connected graph G, tree(G) ≥ ⌊girth(G) / 2⌋ - 1 + max_v l(v) where tree(G) is the number of vertices of a largest induced tree subgraph, girth(G) is the length of the shortest cycle (0 if acyclic), and l(v) = indepNeighbors G v is the independence number of the neighbourhood of v.