Theorem 11.7 (Erdős) — graphs with large girth and large chromatic number
ProvedAppliedComb.Ramsey.high_girth_chromaticThe girth of a graph is the smallest integer for which contains a cycle on vertices; the girth of a forest is infinite. The chromatic number is the least number of colours in a proper colouring of the vertices (adjacent vertices get different colours).
For every pair of integers with there exists a finite simple graph with
Such a graph has no short cycles, so every small neighbourhood looks like a tree, and yet it cannot be coloured with colours. The theorem is the chapter's showcase of the probabilistic method.
Formalization Note. The graph is a SimpleGraph (Fin N) for some . The girth is Mathlib's SimpleGraph.egirth, valued in : the least length of a cycle, with length equal to the number of vertices on the cycle, and () for a forest, exactly as on p. 234. Mathlib's SimpleGraph.girth, which is on forests, is deliberately not used. The chromatic number is SimpleGraph.chromaticNumber, also in and finite on a finite graph. The parameter is taken in : for a negative integer the condition is automatic, so nothing is lost.
import Mathlib
namespace AppliedComb.Ramsey
/-- Theorem 11.7 (Erdős), Keller & Trotter p. 234: for all integers `g, t` with `g ≥ 3` there is
a (finite, simple) graph `G` with `χ(G) > t` and girth greater than `g`. The girth is Mathlib's
`SimpleGraph.egirth`, the least length of a cycle and `⊤` (infinite) for a forest, as on p. 234. -/
theorem high_girth_chromatic (g t : ℕ) (hg : 3 ≤ g) :
∃ (N : ℕ) (G : SimpleGraph (Fin N)),
(t : ℕ∞) < G.chromaticNumber ∧ (g : ℕ∞) < G.egirth := by sorry
end AppliedComb.Ramsey
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let and be natural numbers with . The statement asserts that there exist a natural number and a simple graph on the vertex set such that both of these hold:
Both comparisons are strict and take place in the extended naturals .
- Chromatic number: is the infimum, in , of the numbers for which has a proper colouring with colours (adjacent vertices always get different colours). It would be if no finite works.
- Girth: is the extended girth, the infimum of the lengths of cycles in . It is when has no cycle, i.e. when is a forest.
- Size of : the vertex count is existentially chosen, and nothing is required of it beyond what the two inequalities force.
Degenerate cases:
- : the condition is only , which a single vertex already satisfies (, girth ). The statement is then met by a one-vertex graph.
- : it is met by a single edge (), which has no cycle and so girth .
- Acyclic graphs in general: any acyclic satisfies the girth condition automatically, because its girth is .
- : excluded by the hypothesis , so the statement asserts nothing for those values.
- Empty vertex set: gives , which never exceeds , so the empty graph never witnesses the statement.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.