Written on the Wall II - Conjecture 143 #
Reference: E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc
theorem
WrittenOnTheWallII.GraphConjecture143.conjecture143
{α : Type u_1}
[Fintype α]
[DecidableEq α]
[Nontrivial α]
(G : SimpleGraph α)
[DecidableRel G.Adj]
(h : G.Connected)
(hσ : 0 < G.secondSmallestDegree)
:
WOWII Conjecture 143:
For a simple connected graph $G$, $\mathrm{tree}(G) \ge (\mathrm{girth}(G) + 1) / \sigma(G)$, where $\mathrm{tree}(G)$ is the largest induced tree size, $\mathrm{girth}(G)$ is the length of the shortest cycle, and $\sigma(G) = G.\mathrm{secondSmallestDegree}$ is the second-smallest degree of $G$'s degree sequence (per WOWII defEntry 65). We state the inequality in denominator-free form to avoid the $\sigma = 0$ corner case ($n \le 1$).