Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.28 — interval graphs satisfy χ(G) = ω(G)

Proved
AppliedComb.Graphs.interval_chromatic_eq_clique

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

coloringcombinatoricsgraph-theoryinterval-graphsp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1

Let G=(V,E)G = (V, E)G=(V,E) be a finite interval graph, the intersection graph of a family of closed real intervals indexed by VVV. Then

χ(G)=ω(G),\chi(G) = \omega(G),χ(G)=ω(G),

the chromatic number equals the clique number.

Since induced subgraphs of interval graphs are interval graphs, this shows interval graphs are perfect.

Formalization Note. χ(G)\chi(G)χ(G) is Mathlib's chromaticNumber in N∞\mathbb N_\inftyN∞​ and ω(G)\omega(G)ω(G) is Mathlib's cliqueNum in N\mathbb NN, cast to N∞\mathbb N_\inftyN∞​. On the empty graph both sides are 000.

Preamble
import Mathlib
import Definitions.Def_AppliedComb_Graphs_IsIntervalGraph
Formal statement
namespace AppliedComb.Graphs

/-- Keller–Trotter, p. 87, Theorem 5.28. If `G = (V, E)` is a (finite) interval graph, then
`χ(G) = ω(G)`. -/
theorem interval_chromatic_eq_clique {V : Type*} [Fintype V] (G : SimpleGraph V)
    (hG : IsIntervalGraph G) : G.chromaticNumber = (G.cliqueNum : ℕ∞) := by sorry

end AppliedComb.Graphs
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 87, Theorem 5.28 (interval graph: p. 87)
Read-back

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

Setting. Let VVV be a finite type of vertices, and let GGG be a simple graph on VVV. The theorem assumes GGG is an interval graph. Here that means there are functions a,b:V→Ra, b : V \to \mathbb{R}a,b:V→R with both of these properties:

  • a(v)≤b(v)a(v) \le b(v)a(v)≤b(v) for every vertex vvv;
  • for all distinct u≠vu \ne vu=v,
u∼Gv  ⟺  [a(u),b(u)]∩[a(v),b(v)]≠∅.u \sim_G v \iff [a(u), b(u)] \cap [a(v), b(v)] \ne \varnothing.u∼G​v⟺[a(u),b(u)]∩[a(v),b(v)]=∅.

Conclusion.

χ(G)=ω(G),\chi(G) = \omega(G),χ(G)=ω(G),

with both sides compared in N∪{∞}\mathbb{N} \cup \{\infty\}N∪{∞}.

  • χ(G)\chi(G)χ(G) is Mathlib's chromatic number: the least number of colours in a proper colouring, and ∞\infty∞ if there is none.
  • ω(G)\omega(G)ω(G) 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. It is then regarded as an element of N∪{∞}\mathbb{N} \cup \{\infty\}N∪{∞}.

Degenerate cases.

  • VVV empty: the interval hypothesis holds trivially. χ(G)=0\chi(G) = 0χ(G)=0, and the only clique is the empty set, so ω(G)=0\omega(G) = 0ω(G)=0. The equation holds as 0=00 = 00=0.
  • VVV nonempty with no edges: both sides equal 111.
  • No infinite graphs: the finiteness of VVV is assumed, so the statement does not cover infinite graphs.
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