complete_graph_odd_line_graph_chromatic_number_eq
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
- complete_graph_line_graph_colorableThe line graph of K_n is n-colorable for n ≥ 3.
- complete_graph_odd_line_graph_le_chromaticNumberFor odd n ≥ 3, the chromatic number of the line graph of K_n is at least n.
- Used by 8
- complete_graph_odd_rainbow_matching_third_boundEvery proper edge coloring of an odd complete graph of order n>=3 has a matching with pairwise distinct colors and at least ceil(n/3) edges.
- wild_number_complete_thirteen_eq_iff_permuted_cutsFor every proper 13-coloring of K_13, its wild number is nine if and only if some permutation of the canonical 3+3+3+4 vertex partition…
- odd_complete_min_edge_coloring_missing_vertex_equivIn a minimum proper coloring of an odd complete graph, every color misses exactly one vertex, and these missing vertices give a bijection…
- wild_complete_thirteen_fixed_color_flip_obstructionThere is a normalized minimum proper 13-coloring of K_13 for which the partition {0,1,2},{3,4,5},{6,7,8},{9,10,11,12} has exactly one…
- wild_no_closed_union_of_blocksIf every used color crosses every nonempty proper cut of the block labels under p, then no nonempty proper vertex set that is a union of…
- wild_complete_thirteen_one_swap_repair_obstructionThere exists a minimum proper 13-coloring of K_13, normalized so that color i misses vertex i, with this property. The fixed partition…
- wild_number_complete_graph_formula_iff_odd_ordersThe wild-number sharpness conjecture for minimum proper colorings of every complete graph of order at least three is equivalent to its…
- wild_number_complete_even_eq_of_preceding_oddFor odd n>=3, if every proper n-coloring of K_n has the conjectured sharp wild number, then every minimum proper coloring of K_(n+1) has…
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.
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.
uses
le_antisymm,complete_graph_line_graph_colorable,chromaticNumber_le,complete_graph_odd_line_graph_le_chromaticNumberexact 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.
- The chromatic number in Mathlib is valued in the extended natural numbers (`ℕ∞`), so the natural number `n` is implicitly coerced to `ℕ∞` in the statement and inequalities.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)