Theorem 5.28 — interval graphs satisfy χ(G) = ω(G)
ProvedAppliedComb.Graphs.interval_chromatic_eq_cliqueLet be a finite interval graph, the intersection graph of a family of closed real intervals indexed by . Then
the chromatic number equals the clique number.
Since induced subgraphs of interval graphs are interval graphs, this shows interval graphs are perfect.
Formalization Note. is Mathlib's chromaticNumber in and is Mathlib's cliqueNum in , cast to . On the empty graph both sides are .
import Mathlib import Definitions.Def_AppliedComb_Graphs_IsIntervalGraph
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let be a finite type of vertices, and let be a simple graph on . The theorem assumes is an interval graph. Here that means there are functions with both of these properties:
- for every vertex ;
- for all distinct ,
Conclusion.
with both sides compared in .
- is Mathlib's chromatic number: the least number of colours in a proper colouring, and if there is none.
- is Mathlib's clique number: the supremum, as a natural number, of the sizes for which has a -element set of pairwise adjacent vertices. It is then regarded as an element of .
Degenerate cases.
- empty: the interval hypothesis holds trivially. , and the only clique is the empty set, so . The equation holds as .
- nonempty with no edges: both sides equal .
- No infinite graphs: the finiteness of is assumed, so the statement does not cover infinite graphs.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.