complete_graph_line_graph_colorable
The line graph of K_n is n-colorable for n ≥ 3.
Statement
theorem complete_graph_line_graph_colorable (n : ℕ) (hn : 3 ≤ n) : (⊤ : SimpleGraph (Fin n)).lineGraph.Colorable n- Source
- step towards complete_graph_odd_line_graph_chromatic_number_eq
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- 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…
- complete_graph_odd_line_graph_chromatic_number_eqThe edge chromatic number of an odd complete graph on at least three vertices is its number of vertices.
The proof, explained
The line graph of K_n has the edges of K_n as its vertices, with two edges adjacent when they share an endpoint. We define an explicit n-coloring by assigning to each edge {a, b} the color (a + b) mod n. If two adjacent edges shared an endpoint v, say {v, a} and {v, b}, having the same color would imply v + a ≡ v + b (mod n), which simplifies to a ≡ b (mod n); because a, b < n, this forces a = b and contradicts that the edges are distinct.
An edge coloring function col mapping each unordered pair {a, b} to (a + b) % n is well-defined.
Because n ≥ 3, we have n > 0 (verified by linear arithmetic via omega), so (a + b) % n is strictly less than n by Nat.mod_lt. Since addition of natural numbers is commutative (Nat.add_comm), this operation is symmetric in a and b and lifts via Sym2.lift to a well-defined function from unordered pairs Sym2 (Fin n) to Fin n.
uses
Nat.mod_lt,Nat.add_comm,Sym2.liftlet col : Sym2 (Fin n) → Fin n := Sym2.lift ⟨fun a b => (⟨(a.val + b.val) % n, Nat.mod_lt _ (by omega)⟩ : Fin n), fun a b => by simp [Nat.add_comm]⟩
To show the line graph is n-colorable, it suffices to prove that adjacent edges receive distinct colors under col.
Using SimpleGraph.Coloring.mk, the function col defines a valid coloring of the line graph as long as any two adjacent vertices in the line graph (which are edges of K_n) are assigned distinct colors.
uses
SimpleGraph.Coloring.mkrefine ⟨SimpleGraph.Coloring.mk (fun e => col e.val) ?_⟩
Two adjacent edges e₁ and e₂ in the line graph are distinct and can be written as s(v, a) and s(v, b) for some shared vertex v.
By definition of adjacency in the line graph (SimpleGraph.lineGraph_adj_iff_exists), e₁ ≠ e₂ and they share a common vertex v. Since v is incident to both edges, Sym2.mem_iff_exists.mp allows us to express e₁ as the unordered pair s(v, a) and e₂ as s(v, b) for some vertices a, b ∈ Fin n.
uses
SimpleGraph.lineGraph_adj_iff_exists,Sym2.mem_iff_exists.mpintro e₁ e₂ h rw [SimpleGraph.lineGraph_adj_iff_exists] at h obtain ⟨hne, v, h1, h2⟩ := h obtain ⟨a, ha⟩ : ∃ a, (e₁ : Sym2 (Fin n)) = s(v, a) := (Sym2.mem_iff_exists.mp h1).imp fun a h => h obtain ⟨b, hb⟩ : ∃ b, (e₂ : Sym2 (Fin n)) = s(v, b) := (Sym2.mem_iff_exists.mp h2).imp fun a h => h
Assuming for contradiction that e₁ and e₂ have the same color, it suffices to show s(v, a) = s(v, b).
Assume for contradiction that col(e₁) = col(e₂). To contradict the fact that e₁ ≠ e₂, it suffices by Subtype.ext to prove that the underlying unordered pairs are equal, which after substituting the expressions for e₁ and e₂ means showing s(v, a) = s(v, b).
uses
Subtype.extintro hc apply hne apply Subtype.ext rw [ha, hb]
The equality of colors implies a = b, concluding s(v, a) = s(v, b) and finishing the proof.
Unfolding col on s(v, a) and s(v, b) using Sym2.lift_mk and Fin.mk.injEq simplifies the assumption col(e₁) = col(e₂) to (v + a) % n = (v + b) % n. Cancelling v modulo n via Nat.ModEq.add_left_cancel' yields a ≡ b [MOD n]. Since a, b < n, Nat.ModEq.eq_of_lt_of_lt implies that their underlying natural values are equal, hence a = b in Fin n by Fin.ext. Substituting this yields s(v, a) = s(v, b), contradicting e₁ ≠ e₂.
uses
Sym2.lift_mk,Fin.mk.injEq,Nat.ModEq.add_left_cancel',Nat.ModEq.eq_of_lt_of_lt,Fin.extsimp only [col, ha, hb, Sym2.lift_mk, Fin.mk.injEq] at hc have h3 := Nat.ModEq.add_left_cancel' v.val hc have : a.val = b.val := Nat.ModEq.eq_of_lt_of_lt h3 a.isLt b.isLt rw [Fin.ext this]
Nat.mod_lt- For any natural number x and positive natural number y, the remainder x % y is strictly less than y.
Nat.add_comm- Addition of natural numbers is commutative: n + m = m + n.
Sym2.lift- A symmetric function on pairs lifts to a well-defined function on unordered pairs (Sym2).
SimpleGraph.Coloring.mk- Constructs a proper graph coloring from a function on vertices that assigns different colors to adjacent vertices.
SimpleGraph.lineGraph_adj_iff_exists- Two vertices in the line graph are adjacent if and only if they are distinct edges sharing a common endpoint.
Sym2.mem_iff_exists.mp- If an element v belongs to an unordered pair e, then e = s(v, y) for some y.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
Sym2.lift_mk- The value of a lifted symmetric function on the unordered pair s(a, b) equals the function evaluated at (a, b).
Fin.mk.injEq- Two Fin n elements are equal if and only if their underlying natural values are equal.
Nat.ModEq.add_left_cancel'- Additive cancellation in modular arithmetic: c + a ≡ c + b [MOD n] implies a ≡ b [MOD n].
Nat.ModEq.eq_of_lt_of_lt- Two natural numbers strictly less than m that are congruent modulo m are equal.
Fin.ext- Two elements of Fin n are equal if their numerical values are equal.
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.
/-- The line graph of K_n is n-colorable for n ≥ 3. -/theorem complete_graph_line_graph_colorable (n : ℕ) (hn : 3 ≤ n) : (⊤ : SimpleGraph (Fin n)).lineGraph.Colorable n := by let col : Sym2 (Fin n) → Fin n := Sym2.lift ⟨fun a b => (⟨(a.val + b.val) % n, Nat.mod_lt _ (by omega)⟩ : Fin n), fun a b => by simp [Nat.add_comm]⟩ refine ⟨SimpleGraph.Coloring.mk (fun e => col e.val) ?_⟩ intro e₁ e₂ h rw [SimpleGraph.lineGraph_adj_iff_exists] at h obtain ⟨hne, v, h1, h2⟩ := h obtain ⟨a, ha⟩ : ∃ a, (e₁ : Sym2 (Fin n)) = s(v, a) := (Sym2.mem_iff_exists.mp h1).imp fun a h => h obtain ⟨b, hb⟩ : ∃ b, (e₂ : Sym2 (Fin n)) = s(v, b) := (Sym2.mem_iff_exists.mp h2).imp fun a h => h intro hc apply hne apply Subtype.ext rw [ha, hb] simp only [col, ha, hb, Sym2.lift_mk, Fin.mk.injEq] at hc have h3 := Nat.ModEq.add_left_cancel' v.val hc have : a.val = b.val := Nat.ModEq.eq_of_lt_of_lt h3 a.isLt b.isLt rw [Fin.ext this]