AFTD Auto-Formalizing Theoretical Domains

complete_graph_odd_line_graph_le_chromaticNumber

theoremverified

For odd n ≥ 3, the chromatic number of the line graph of K_n is at least n.

Statement

theorem complete_graph_odd_line_graph_le_chromaticNumber (n : ℕ) (hn : 3 ≤ n) (hodd : n % 2 = 1) : n ≤ (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber
Source
step towards complete_graph_odd_line_graph_chromatic_number_eq
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

To prove that the chromatic number of the line graph of $K_n$ is at least $n$ for odd $n \ge 3$, it suffices to show that any proper edge-coloring of $K_n$ uses at least $n$ colors. Fixing an arbitrary vertex $v$, the $n - 1$ edges incident to $v$ share an endpoint, so they must receive $n - 1$ pairwise distinct colors. Because $n$ is odd, no matching can be perfect, and a helper lemma guarantees the existence of an edge whose color does not appear at $v$ at all. Thus the set of colors incident to $v$ is a strict subset of the available colors, which forces the total number of colors to exceed $n - 1$, hence to be at least $n$.

  1. To show that the line graph of $K_n$ has chromatic number at least $n$, it suffices to show that any proper coloring with $k$ colors satisfies $n \le k$.

    By `SimpleGraph.le_chromaticNumber_iff_coloring`, bounding the chromatic number from below by $n$ is equivalent to showing that any proper coloring using $k$ colors must have $k \ge n$. We introduce an arbitrary color count $k$ and proper coloring $c$.

    lines 3–5

    uses SimpleGraph.le_chromaticNumber_iff_coloring

      classical
      rw [SimpleGraph.le_chromaticNumber_iff_coloring]
      intro k c
  2. Fix a vertex $v = 0$ and define $C_v$ to be the set of colors assigned to the edges incident to $v$.

    Since $n \ge 3$, vertex $0 \in \mathrm{Fin}\, n$ exists. We check that $0 \ne 1$ (using `Fin.ext_iff`) to construct a fallback color $i_0 = c(\{0, 1\})$. The set $C_v$ is then defined as the image of $V \setminus \{v\}$ under the function sending each vertex $x \ne v$ to the color $c(\{v, x\})$, which is a valid edge by `wild_kn_mem`.

    lines 6–9

    uses Fin.ext_iff, wild_kn_mem

      let v : Fin n := ⟨0, by omega⟩
      have h01 : (⟨0, by omega⟩ : Fin n) ≠ ⟨1, by omega⟩ := by simp [Fin.ext_iff]
      let i0 := c ⟨s(⟨0, by omega⟩, ⟨1, by omega⟩), wild_kn_mem h01⟩
      let Cv := (Finset.univ.erase v).image (fun x => if h : v ≠ x then c ⟨s(v,x),wild_kn_mem h⟩ else i0)
  3. The set of colors incident to $v$ has cardinality $|C_v| = n - 1$.

    The set of vertices other than $v$ has cardinality $n - 1$ by `Finset.card_erase_of_mem` and `Fintype.card_fin`. The coloring map on $V \setminus \{v\}$ is injective: if two incident edges $\{v, a\}$ and $\{v, b\}$ have the same color, `wild_kn_same_color` implies $a = b$, since distinct edges sharing an endpoint are adjacent in the line graph and cannot have the same color. Hence $|C_v| = n - 1$ by `Finset.card_image_of_injOn`.

    lines 10–18

    uses Finset.card_image_of_injOn, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ, Fintype.card_fin, Ne.symm, Finset.ne_of_mem_erase, dif_pos, wild_kn_same_color

      have hcard : Cv.card = n-1 := by
        dsimp only [Cv]
        rw [Finset.card_image_of_injOn, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ,
          Fintype.card_fin]
        intro a ha b hb hab
        have ha' := Ne.symm (Finset.ne_of_mem_erase ha)
        have hb' := Ne.symm (Finset.ne_of_mem_erase hb)
        simp only [dif_pos ha', dif_pos hb'] at hab
        exact wild_kn_same_color c ha' hb' hab
  4. There exists an edge $e$ whose color $c(e)$ is not in $C_v$.

    Because $n \ge 3$ is odd, `wild_kn_exists_missing_color_of_odd` provides an edge $e$ whose color differs from every edge incident to $v$. If $c(e) \in C_v$, then by `Finset.mem_image.1` it would equal $c(\{v, x\})$ for some $x \ne v$, a contradiction.

    lines 19–25

    uses wild_kn_exists_missing_color_of_odd, Finset.mem_image.1, Ne.symm, Finset.ne_of_mem_erase, dif_pos

      obtain ⟨e, he⟩ := wild_kn_exists_missing_color_of_odd hn hodd c v
      have hmiss : c e ∉ Cv := by
        intro hi
        obtain ⟨x,hx,hcol⟩ := Finset.mem_image.1 hi
        have hvx : v ≠ x := Ne.symm (Finset.ne_of_mem_erase hx)
        simp only [dif_pos hvx] at hcol
        exact he x hvx hcol
  5. The total number of colors $k$ is at least $n$.

    Because $c(e)$ is one of the $k$ colors but $c(e) \notin C_v$, $C_v$ is a strict subset of the set of all $k$ colors by `Finset.ssubset_iff_subset_ne.2`. By `Finset.card_lt_card`, $|C_v| < k$, which means $n - 1 < k$. Linear arithmetic over the natural numbers then immediately implies $n \le k$.

    lines 26–30

    uses Finset.ssubset_iff_subset_ne.2, Finset.subset_univ, Finset.mem_univ, Finset.card_lt_card, Finset.card_univ, Fintype.card_fin

      have hstrict : Cv ⊂ Finset.univ := Finset.ssubset_iff_subset_ne.2
        ⟨Finset.subset_univ _, fun h => hmiss (h ▸ Finset.mem_univ _)⟩
      have hi := Finset.card_lt_card hstrict
      rw [hcard, Finset.card_univ, Fintype.card_fin] at hi
      exact_mod_cast (show n ≤ k by omega)
SimpleGraph.le_chromaticNumber_iff_coloring
The chromatic number of a graph is at least $n$ if and only if every proper coloring of the graph with $m$ colors satisfies $n \le m$.
Fin.ext_iff
Two elements of `Fin n` are equal if and only if their underlying natural numbers are equal.
wild_kn_mem
In the complete graph $K_n$, any two distinct vertices form an edge.
Finset.card_image_of_injOn
The image of a finite set under an injective map has the same cardinality as the set.
Finset.card_erase_of_mem
Removing an element from a finite set decreases its cardinality by 1.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.card_univ
The cardinality of the universal finset of a finite type is the cardinality of the type itself.
Fintype.card_fin
The cardinality of `Fin n` is $n$.
Ne.symm
Inequality is symmetric: if $a \ne b$, then $b \ne a$.
Finset.ne_of_mem_erase
An element in $s \setminus \{a\}$ is not equal to $a$.
dif_pos
A dependent if-then-else evaluates to the `then` branch when the condition holds.
wild_kn_same_color
In a proper coloring of the line graph of $K_n$, two edges sharing an endpoint cannot have the same color unless they are the same edge.
wild_kn_exists_missing_color_of_odd
For odd $n \ge 3$, any proper line-graph coloring of $K_n$ contains an edge whose color does not appear on any edge incident to a given vertex.
Finset.mem_image.1
If an element belongs to the image $f(s)$, then it equals $f(x)$ for some $x \in s$.
Finset.ssubset_iff_subset_ne.2
A subset $s \subseteq t$ is a strict subset ($s \subsetneq t$) if $s \ne t$.
Finset.subset_univ
Every finset of a finite type is a subset of the universal finset.
Finset.card_lt_card
A strict subset of a finite set has strictly smaller cardinality than the set.

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

/-- For odd n ≥ 3, the chromatic number of the line graph of K_n is at least n. -/theorem complete_graph_odd_line_graph_le_chromaticNumber (n : ℕ) (hn : 3 ≤ n) (hodd : n % 2 = 1) : n ≤ (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber := by  classical  rw [SimpleGraph.le_chromaticNumber_iff_coloring]  intro k c  let v : Fin n := ⟨0, by omega⟩  have h01 : (⟨0, by omega⟩ : Fin n) ≠ ⟨1, by omega⟩ := by simp [Fin.ext_iff]  let i0 := c ⟨s(⟨0, by omega⟩, ⟨1, by omega⟩), wild_kn_mem h01⟩  let Cv := (Finset.univ.erase v).image (fun x => if h : v ≠ x then c ⟨s(v,x),wild_kn_mem h⟩ else i0)  have hcard : Cv.card = n-1 := by    dsimp only [Cv]    rw [Finset.card_image_of_injOn, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ,      Fintype.card_fin]    intro a ha b hb hab    have ha' := Ne.symm (Finset.ne_of_mem_erase ha)    have hb' := Ne.symm (Finset.ne_of_mem_erase hb)    simp only [dif_pos ha', dif_pos hb'] at hab    exact wild_kn_same_color c ha' hb' hab  obtain ⟨e, he⟩ := wild_kn_exists_missing_color_of_odd hn hodd c v  have hmiss : c e ∉ Cv := by    intro hi    obtain ⟨x,hx,hcol⟩ := Finset.mem_image.1 hi    have hvx : v ≠ x := Ne.symm (Finset.ne_of_mem_erase hx)    simp only [dif_pos hvx] at hcol    exact he x hvx hcol  have hstrict : Cv ⊂ Finset.univ := Finset.ssubset_iff_subset_ne.2    ⟨Finset.subset_univ _, fun h => hmiss (h ▸ Finset.mem_univ _)⟩  have hi := Finset.card_lt_card hstrict  rw [hcard, Finset.card_univ, Fintype.card_fin] at hi  exact_mod_cast (show n ≤ k by omega)
See it in the graphDiscuss this resultChallenge it