Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 11.7 (Erdős) — graphs with large girth and large chromatic number

Proved
AppliedComb.Ramsey.high_girth_chromatic

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theoryp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1probability

The girth of a graph GGG is the smallest integer ggg for which GGG contains a cycle on ggg vertices; the girth of a forest is infinite. The chromatic number χ(G)\chi(G)χ(G) is the least number of colours in a proper colouring of the vertices (adjacent vertices get different colours).

For every pair g,tg, tg,t of integers with g≥3g \ge 3g≥3 there exists a finite simple graph GGG with

χ(G)>tandgirth⁡(G)>g.\chi(G) > t \qquad\text{and}\qquad \operatorname{girth}(G) > g.χ(G)>tandgirth(G)>g.

Such a graph has no short cycles, so every small neighbourhood looks like a tree, and yet it cannot be coloured with ttt colours. The theorem is the chapter's showcase of the probabilistic method.

Formalization Note. The graph is a SimpleGraph (Fin N) for some NNN. The girth is Mathlib's SimpleGraph.egirth, valued in N∪{∞}\mathbb N \cup \{\infty\}N∪{∞}: the least length of a cycle, with length equal to the number of vertices on the cycle, and ∞\infty∞ (⊤\top⊤) for a forest, exactly as on p. 234. Mathlib's SimpleGraph.girth, which is 000 on forests, is deliberately not used. The chromatic number is SimpleGraph.chromaticNumber, also in N∪{∞}\mathbb N \cup \{\infty\}N∪{∞} and finite on a finite graph. The parameter ttt is taken in N\mathbb NN: for a negative integer ttt the condition χ(G)>t\chi(G) > tχ(G)>t is automatic, so nothing is lost.

Preamble
import Mathlib
Formal statement
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
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 234, Theorem 11.7 (girth defined on the same page)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let ggg and ttt be natural numbers with g≥3g \ge 3g≥3. The statement asserts that there exist a natural number NNN and a simple graph GGG on the vertex set {0,1,…,N−1}\{0,1,\dots,N-1\}{0,1,…,N−1} such that both of these hold:

t<χ(G)andg<girth⁡(G).t < \chi(G) \qquad\text{and}\qquad g < \operatorname{girth}(G).t<χ(G)andg<girth(G).

Both comparisons are strict and take place in the extended naturals N∪{∞}\mathbb{N}\cup\{\infty\}N∪{∞}.

  • Chromatic number: χ(G)\chi(G)χ(G) is the infimum, in N∪{∞}\mathbb{N}\cup\{\infty\}N∪{∞}, of the numbers kkk for which GGG has a proper colouring with kkk colours (adjacent vertices always get different colours). It would be ∞\infty∞ if no finite kkk works.
  • Girth: girth⁡(G)\operatorname{girth}(G)girth(G) is the extended girth, the infimum of the lengths of cycles in GGG. It is ∞\infty∞ when GGG has no cycle, i.e. when GGG is a forest.
  • Size of GGG: the vertex count NNN is existentially chosen, and nothing is required of it beyond what the two inequalities force.

Degenerate cases:

  • t=0t = 0t=0: the condition is only χ(G)>0\chi(G) > 0χ(G)>0, which a single vertex already satisfies (χ=1\chi = 1χ=1, girth ∞\infty∞). The statement is then met by a one-vertex graph.
  • t=1t = 1t=1: it is met by a single edge (χ=2\chi = 2χ=2), which has no cycle and so girth ∞>g\infty > g∞>g.
  • Acyclic graphs in general: any acyclic GGG satisfies the girth condition automatically, because its girth is ∞\infty∞.
  • g≤2g \le 2g≤2: excluded by the hypothesis g≥3g \ge 3g≥3, so the statement asserts nothing for those values.
  • Empty vertex set: N=0N = 0N=0 gives χ(G)=0\chi(G) = 0χ(G)=0, which never exceeds ttt, so the empty graph never witnesses the statement.
Human review
  • Endorsed by Shuze Chen · Oct 2, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 2, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me