Theorem 2 (Erdős–Gallai), p. 2 — a graph with no cycle longer than k has at most k(n−1)/2 edges (corrected)
ProvedEvenCycleTuran.EvenCount.theorem_2Let and let be a graph on vertices that contains no cycle of length greater than . Then
This is the Erdős–Gallai bound on the number of edges of a graph of circumference at most . In the paper it is the input to Claim 1, applied to the edges inside and next to the neighbourhood of a vertex of a -free graph.
Formalization Note The paper prints the bound as , which is false: two triangles sharing a vertex (, ) have edges. The statement here is the bound Erdős and Gallai proved; Claim 1 needs only for circumference , which the corrected bound gives. The hypothesis is added: for "no cycle longer than " means a forest, which may have edges. The bound is stated as in (at both sides are ).
import Mathlib import Definitions.Def_EvenCycleTuran_EvenCount_Setting
namespace EvenCycleTuran.EvenCount
open Finset SimpleGraph
theorem theorem_2 (n k : ℕ) (hk : 2 ≤ k) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
(hG : ∀ a : ℕ, k < a → (cycleGraph a).Free G) :
2 * #G.edgeFinset ≤ k * (n - 1) := by sorry
end EvenCycleTuran.EvenCount
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.