Proposition 5.25 — for every t ≥ 3 there is a graph with χ = t and ω = 2
ProvedAppliedComb.Graphs.triangle_free_chromaticFor every integer there is a finite graph with
where is the chromatic number and 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 (Fin N) for some . is Mathlib's chromaticNumber (-valued, equal to the book's value on finite graphs) and is Mathlib's cliqueNum. Both equalities are exact, as on the page.
import Mathlib
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let be a natural number with .
Conclusion. There exist a natural number and a simple graph on the vertex set such that both of the following hold:
- . This is Mathlib's chromatic number, valued in : the least number of colours in a proper colouring, and if there is none.
- . This is Mathlib's clique number: the supremum, as a natural number, of the sizes for which has a -element set of pairwise adjacent vertices.
Because the vertex set is finite, means exactly that has at least one edge and no three pairwise adjacent vertices.
Degenerate cases.
- : excluded by the hypothesis. The theorem says nothing about these values.
- The witness: is not bounded in the statement, and nothing is said about the graph beyond these two numbers.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.