complete_graph_odd_line_graph_le_chromaticNumber
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
- wild_number_complete_graph_min_proper_coloring_geLet n ≥ 3 and let ρ be a minimum proper edge colouring of K_n (a proper colouring with χ'(K_n) colours). Then wld_ρ(K_n) ≥ ⌊4⌈n/2⌉/3⌋.
- Used by 1
- 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
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$.
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$.
uses
SimpleGraph.le_chromaticNumber_iff_coloringclassical rw [SimpleGraph.le_chromaticNumber_iff_coloring] intro k c
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`.
uses
Fin.ext_iff,wild_kn_memlet 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)
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`.
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_colorhave 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
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.
uses
wild_kn_exists_missing_color_of_odd,Finset.mem_image.1,Ne.symm,Finset.ne_of_mem_erase,dif_posobtain ⟨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
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$.
uses
Finset.ssubset_iff_subset_ne.2,Finset.subset_univ,Finset.mem_univ,Finset.card_lt_card,Finset.card_univ,Fintype.card_finhave 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.
- The proof relies on the helper lemma `wild_kn_exists_missing_color_of_odd`, which captures the combinatorial property that for odd n, no matching can cover all vertices, so every color class misses at least one vertex (and in particular some color is absent from the edges incident to any chosen vertex).
- The set $C_v$ of colors at vertex $v$ is formally defined via a dependent if-then-else with a default color $i_0$ to provide a total function on $V \setminus \{v\}$ before taking the image.
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.
/-- 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)