Theorem 5.21 — a graph is 2-colorable iff it contains no odd cycle
ProvedAppliedComb.Graphs.two_colorable_iffLet be a finite graph and its chromatic number, the least for which has a proper coloring with colors. Then
where an odd cycle is a sequence of distinct vertices, odd, with an edge for and an edge.
This characterizes bipartite graphs and makes 2-colorability easy to recognize.
Formalization Note. is Mathlib's SimpleGraph.chromaticNumber (valued in ), which on a finite graph is the book's least number of colors. The obstruction is an odd cycle in the book's sense (distinct vertices), not an odd closed walk.
import Mathlib import Definitions.Def_AppliedComb_Graphs_IsCycle
namespace AppliedComb.Graphs
/-- Keller–Trotter, p. 82, Theorem 5.21. A (finite) graph is 2-colorable, i.e. `χ(G) ≤ 2`, if
and only if it does not contain an odd cycle (a cycle of `n ≥ 3` distinct vertices with `n`
odd, p. 71). -/
theorem two_colorable_iff {V : Type*} [Fintype V] (G : SimpleGraph V) :
G.chromaticNumber ≤ 2 ↔ ¬ ContainsOddCycle G := 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 .
Conclusion. The theorem states:
The two sides mean the following.
- is Mathlib's chromatic number. It is valued in and equals the least such that has a proper colouring with colours. It would be if no such existed, but that cannot happen for finite .
- Contains an odd cycle: there is a list of pairwise distinct vertices satisfying all of these:
- ;
- is odd;
- for ;
- .
Degenerate cases.
- empty: and there are no cycles, so both sides are true.
- Edgeless graph: and there are no cycles, so both sides are true.
- Fewer than 3 vertices: there are no cycles, and holds.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.