AFTD Auto-Formalizing Theoretical Domains

complete_graph_odd_line_graph_chromatic_number_eq

theoremverified

The edge chromatic number of an odd complete graph on at least three vertices is its number of vertices.

Statement

theorem complete_graph_odd_line_graph_chromatic_number_eq (n : ℕ) (hn : 3 ≤ n) (hodd : n % 2 = 1) : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = n
Source
Standard complete-graph edge-coloring fact used by arXiv:2610.22142, Section 3, and needed for the proposed OP-306 permutation-event normalization.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 8

The proof, explained

The edge chromatic number of an odd complete graph on n ≥ 3 vertices is proved to equal n by antisymmetry. The upper bound follows from the line graph being n-colorable, while the lower bound is provided by a lemma showing that odd complete graphs require at least n colors for their edges.

  1. The line graph of the complete graph on n vertices has chromatic number equal to n.

    By the antisymmetry of the partial order (`le_antisymm`), it suffices to show both inequalities between the chromatic number and n. For the upper bound, the line graph of K_n is n-colorable by `complete_graph_line_graph_colorable`, so its chromatic number is at most n by `chromaticNumber_le`. For the lower bound, `complete_graph_odd_line_graph_le_chromaticNumber` shows that n is at most the chromatic number, using the hypotheses that n ≥ 3 and n is odd.

    lines 2–3

    uses le_antisymm, complete_graph_line_graph_colorable, chromaticNumber_le, complete_graph_odd_line_graph_le_chromaticNumber

      exact le_antisymm (complete_graph_line_graph_colorable n hn).chromaticNumber_le
        (complete_graph_odd_line_graph_le_chromaticNumber n hn hodd)
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
complete_graph_line_graph_colorable
For n ≥ 3, the line graph of the complete graph on n vertices is n-colorable.
chromaticNumber_le
If a simple graph is n-colorable, then its chromatic number is at most n.
complete_graph_odd_line_graph_le_chromaticNumber
For odd n ≥ 3, the chromatic number of the line graph of the complete graph on n vertices is at least n.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem complete_graph_odd_line_graph_chromatic_number_eq (n : ℕ) (hn : 3 ≤ n) (hodd : n % 2 = 1) : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = n := by  exact le_antisymm (complete_graph_line_graph_colorable n hn).chromaticNumber_le    (complete_graph_odd_line_graph_le_chromaticNumber n hn hodd)
See it in the graphDiscuss this resultChallenge it