AFTD Auto-Formalizing Theoretical Domains

complete_graph_line_graph_colorable

theoremverified

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

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.

  1. 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.

    lines 3–4

    uses Nat.mod_lt, Nat.add_comm, Sym2.lift

      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]⟩
  2. 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.

    line 5

    uses SimpleGraph.Coloring.mk

      refine ⟨SimpleGraph.Coloring.mk (fun e => col e.val) ?_⟩
  3. 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.

    lines 6–10

    uses SimpleGraph.lineGraph_adj_iff_exists, Sym2.mem_iff_exists.mp

      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
  4. 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).

    lines 11–14

    uses Subtype.ext

      intro hc
      apply hne
      apply Subtype.ext
      rw [ha, hb]
  5. 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₂.

    lines 15–18

    uses Sym2.lift_mk, Fin.mk.injEq, Nat.ModEq.add_left_cancel', Nat.ModEq.eq_of_lt_of_lt, Fin.ext

      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]
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

/-- 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]
See it in the graphDiscuss this resultChallenge it