Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 5.25 — for every t ≥ 3 there is a graph with χ = t and ω = 2

Proved
AppliedComb.Graphs.triangle_free_chromatic

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

coloringcombinatoricsgraph-theoryp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1

For every integer t≥3t \ge 3t≥3 there is a finite graph GtG_tGt​ with

χ(Gt)=tandω(Gt)=2,\chi(G_t) = t \quad\text{and}\quad \omega(G_t) = 2,χ(Gt​)=tandω(Gt​)=2,

where χ\chiχ is the chromatic number and ω\omegaω the clique number (the largest size of a set of pairwise adjacent vertices).

So chromatic number and clique number can be arbitrarily far apart: triangle-free graphs can need arbitrarily many colors (Kelly–Kelly; Mycielski).

Formalization Note. The graph lives on the vertex set {0,…,N−1}\{0, \dots, N-1\}{0,…,N−1} (Fin N) for some NNN. χ\chiχ is Mathlib's chromaticNumber (N∞\mathbb N_\inftyN∞​-valued, equal to the book's value on finite graphs) and ω\omegaω is Mathlib's cliqueNum. Both equalities are exact, as on the page.

Preamble
import Mathlib
Formal statement
namespace AppliedComb.Graphs

/-- Keller–Trotter, p. 85, Proposition 5.25. For every `t ≥ 3` there is a (finite) graph `G_t`
with `χ(G_t) = t` and `ω(G_t) = 2`. The graph is taken on the vertex set `Fin N` for some `N`. -/
theorem triangle_free_chromatic (t : ℕ) (ht : 3 ≤ t) :
    ∃ (N : ℕ) (G : SimpleGraph (Fin N)), G.chromaticNumber = t ∧ G.cliqueNum = 2 := by sorry

end AppliedComb.Graphs
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 85, Proposition 5.25 (clique number: p. 84)
Read-back

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

Setting. Let ttt be a natural number with t≥3t \ge 3t≥3.

Conclusion. 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 the following hold:

  • χ(G)=t\chi(G) = tχ(G)=t. This is Mathlib's chromatic number, valued in N∪{∞}\mathbb{N} \cup \{\infty\}N∪{∞}: the least number of colours in a proper colouring, and ∞\infty∞ if there is none.
  • ω(G)=2\omega(G) = 2ω(G)=2. This is Mathlib's clique number: the supremum, as a natural number, of the sizes kkk for which GGG has a kkk-element set of pairwise adjacent vertices.

Because the vertex set is finite, ω(G)=2\omega(G) = 2ω(G)=2 means exactly that GGG has at least one edge and no three pairwise adjacent vertices.

Degenerate cases.

  • t≤2t \le 2t≤2: excluded by the hypothesis. The theorem says nothing about these values.
  • The witness: NNN is not bounded in the statement, and nothing is said about the graph beyond these two numbers.
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