Written on the Wall II - Conjecture 144

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

theorem WrittenOnTheWallII.GraphConjecture144.conjecture144 {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) (h : G.Connected) : ↑G.girth - 1 + ↑(G.ecc G.center) ≤ ↑G.largestInducedTreeSize

WOWII Conjecture 144

For a simple connected graph $G$, $\mathrm{tree}(G) \ge \mathrm{girth}(G) - 1 + \mathrm{ecc}(\mathrm{Centers})$ where $\mathrm{tree}(G)$ is the largest induced tree size, $\mathrm{girth}(G)$ is the length of the shortest cycle ($0$ if acyclic), $\mathrm{Centers} = G.\mathrm{center}$ is the set of vertices with minimum eccentricity (the center of $G$), and $\mathrm{ecc}(\mathrm{Centers})$ is the eccentricity of the center set — the maximum distance from any non-center vertex to the nearest center vertex.