subdivided_k33_line_graph_chromatic_number_eq_four
The line graph of the graph obtained by subdividing one edge of K3,3 once has chromatic number exactly four.
Statement
theorem subdivided_k33_line_graph_chromatic_number_eq_four : h_subdivided_k33.lineGraph.chromaticNumber = 4- Source
- Helper for arXiv:2610.32404 Proposition 11.2 (PR-412).
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- h_subdivided_k33The 7-vertex graph obtained by subdividing one edge of the complete bipartite graph K_{3,3} exactly once.
- Used by 1
- subdivided_k33_line_graph_isk4_diamond_free_four_chromaticLet H be the graph obtained from K3,3 by subdividing one edge exactly once, and let G be its line graph. Then G has no induced subdivision…
The proof, explained
The theorem establishes that the line graph of $K_{3,3}$ with one subdivided edge has chromatic number exactly 4. By the standard characterization of the chromatic number, this is equivalent to showing that the line graph is 4-colorable but not 3-colorable. 4-colorability is proved by explicitly defining a 4-coloring on the 10 edges and verifying that incident edges receive distinct colors; non-3-colorability is proved by extracting the 19 line-graph adjacency inequalities on any hypothetical 3-coloring and showing via exhaustive case analysis that no valid assignment exists.
The coloring function `gcol` is well-defined and symmetric on pairs of vertices. automation
The definition `gcol` explicitly assigns one of the four colors in $\mathrm{Fin}\ 4$ to each of the ten edges of the subdivided $K_{3,3}$ graph (and defaults to 0). Because every branch tests both $(a = u \land b = v)$ and $(a = v \land b = u)$, the function is symmetric; Lean verifies this for all 49 pairs in $\mathrm{Fin}\ 7 \times \mathrm{Fin}\ 7$ by direct computation (`decide`).
private def subdivided_k33_line_graph_chromatic_number_eq_four_gcol (a b : Fin 7) : Fin 4 := if (a = 0 ∧ b = 6) ∨ (a = 6 ∧ b = 0) then 0 else if (a = 3 ∧ b = 6) ∨ (a = 6 ∧ b = 3) then 3 else if (a = 0 ∧ b = 4) ∨ (a = 4 ∧ b = 0) then 1 else if (a = 0 ∧ b = 5) ∨ (a = 5 ∧ b = 0) then 2 else if (a = 1 ∧ b = 3) ∨ (a = 3 ∧ b = 1) then 2 else if (a = 1 ∧ b = 4) ∨ (a = 4 ∧ b = 1) then 0 else if (a = 1 ∧ b = 5) ∨ (a = 5 ∧ b = 1) then 1 else if (a = 2 ∧ b = 3) ∨ (a = 3 ∧ b = 2) then 1 else if (a = 2 ∧ b = 4) ∨ (a = 4 ∧ b = 2) then 2 else if (a = 2 ∧ b = 5) ∨ (a = 5 ∧ b = 2) then 0 else 0 private lemma subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm : ∀ a b : Fin 7, subdivided_k33_line_graph_chromatic_number_eq_four_gcol a b = subdivided_k33_line_graph_chromatic_number_eq_four_gcol b a := by decide
The neighbor sets of all seven vertices in the subdivided graph are fully determined.
For each vertex $0 \dots 6$, unfolding the graph definition with `SimpleGraph.fromRel` and applying linear arithmetic (`omega`) characterizes its exact neighbors: vertices $0, 1, 2, 3, 4, 5$ each have degree 3, and vertex 6 (the subdivision vertex) has degree 2 with neighbors 0 and 3.
uses
SimpleGraph.fromRelprivate lemma subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne : ∀ v x y : Fin 7, h_subdivided_k33.Adj v x → h_subdivided_k33.Adj v y → x ≠ y → subdivided_k33_line_graph_chromatic_number_eq_four_gcol v x ≠ subdivided_k33_line_graph_chromatic_number_eq_four_gcol v y := by have h0 : ∀ x : Fin 7, h_subdivided_k33.Adj (0:Fin 7) x → (x = 6 ∨ x = 4 ∨ x = 5) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h1 : ∀ x : Fin 7, h_subdivided_k33.Adj (1:Fin 7) x → (x = 3 ∨ x = 4 ∨ x = 5) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h2 : ∀ x : Fin 7, h_subdivided_k33.Adj (2:Fin 7) x → (x = 3 ∨ x = 4 ∨ x = 5) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h3 : ∀ x : Fin 7, h_subdivided_k33.Adj (3:Fin 7) x → (x = 6 ∨ x = 1 ∨ x = 2) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h4 : ∀ x : Fin 7, h_subdivided_k33.Adj (4:Fin 7) x → (x = 0 ∨ x = 1 ∨ x = 2) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h5 : ∀ x : Fin 7, h_subdivided_k33.Adj (5:Fin 7) x → (x = 0 ∨ x = 1 ∨ x = 2) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h6 : ∀ x : Fin 7, h_subdivided_k33.Adj (6:Fin 7) x → (x = 0 ∨ x = 3) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega
Distinct edges incident to the same vertex are assigned different colors by `gcol`. automation
Given a vertex $v$ and two distinct neighbors $x \neq y$, we case-split on $v \in \mathrm{Fin}\ 7$ using `fin_cases v`. For each vertex, substituting the known possible neighbors from the previous characterization yields all pairs of incident edges, and in every branch `simp_all` evaluates `gcol` to verify that the two colors differ.
intro v x y hx hy hxy fin_cases v · rcases h0 x hx with rfl | rfl | rfl <;> rcases h0 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h1 x hx with rfl | rfl | rfl <;> rcases h1 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h2 x hx with rfl | rfl | rfl <;> rcases h2 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h3 x hx with rfl | rfl | rfl <;> rcases h3 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h4 x hx with rfl | rfl | rfl <;> rcases h4 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h5 x hx with rfl | rfl | rfl <;> rcases h5 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h6 x hx with rfl | rfl <;> rcases h6 y hy with rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol]
Two distinct edges sharing a vertex have different colors under `gcol`.
Let $s(a, b)$ and $s(c, d)$ be distinct edges sharing a vertex $v$. By `Sym2.mem_iff`, $v$ is either $a$ or $b$, and also either $c$ or $d$. In all four combinations, substituting the common endpoint and using symmetry (`subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm` and `Sym2.eq_swap`) reduces the claim to `subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne`.
uses
Sym2.mem_iff,subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne,subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm,Sym2.eq_swapprivate lemma subdivided_k33_line_graph_chromatic_number_eq_four_edge_col_aux : ∀ (a b c d v : Fin 7), h_subdivided_k33.Adj a b → h_subdivided_k33.Adj c d → v ∈ s(a,b) → v ∈ s(c,d) → s(a,b) ≠ s(c,d) → subdivided_k33_line_graph_chromatic_number_eq_four_gcol a b ≠ subdivided_k33_line_graph_chromatic_number_eq_four_gcol c d := by intro a b c d v hab hcd hv1 hv2 hne rw [Sym2.mem_iff] at hv1 hv2 rcases hv1 with hva | hvb · subst v rcases hv2 with hac | had · subst c exact subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne a b d hab hcd (by intro h; exact hne (by rw [h])) · subst d rw [subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm c a] exact subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne a b c hab hcd.symm (by rintro rfl; exact hne Sym2.eq_swap) · subst v rcases hv2 with hbc | hbd · subst c rw [subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm a b] exact subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne b a d hab.symm hcd (by rintro rfl; exact hne Sym2.eq_swap) · subst d rw [subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm a b, subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm c b] exact subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne b a c hab.symm hcd.symm (by rintro rfl; exact hne rfl)
The line graph of the subdivided $K_{3,3}$ graph is 4-colorable.
We construct a proper 4-coloring of the line graph using `SimpleGraph.Coloring.mk`. Lifting `gcol` to unordered pairs via `Sym2.lift`, any two adjacent vertices in the line graph correspond to distinct edges sharing a vertex $v$. Using `Sym2.mk_surjective` to write them as pairs and `SimpleGraph.mem_edgeSet` to relate them to graph adjacency, the auxiliary lemma `subdivided_k33_line_graph_chromatic_number_eq_four_edge_col_aux` guarantees they receive distinct colors.
uses
SimpleGraph.Coloring.mk,Sym2.lift,subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm,Sym2.mk_surjective,SimpleGraph.mem_edgeSet,Subtype.ext,Sym2.lift_mk,subdivided_k33_line_graph_chromatic_number_eq_four_edge_col_auxprivate lemma subdivided_k33_line_graph_chromatic_number_eq_four_colorable_four : h_subdivided_k33.lineGraph.Colorable 4 := by refine ⟨SimpleGraph.Coloring.mk (fun e : ↑h_subdivided_k33.edgeSet => Sym2.lift ⟨subdivided_k33_line_graph_chromatic_number_eq_four_gcol, subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm⟩ (e : Sym2 (Fin 7))) ?_⟩ intro e1 e2 hAdj obtain ⟨hne, v, hv1, hv2⟩ := hAdj obtain ⟨⟨a, b⟩, hab⟩ := Sym2.mk_surjective (e1 : Sym2 (Fin 7)) obtain ⟨⟨c, d⟩, hcd⟩ := Sym2.mk_surjective (e2 : Sym2 (Fin 7)) have hab' : s(a, b) = (e1 : Sym2 (Fin 7)) := hab have hcd' : s(c, d) = (e2 : Sym2 (Fin 7)) := hcd have h1' : h_subdivided_k33.Adj a b := by have hmem : Sym2.mk a b ∈ h_subdivided_k33.edgeSet := hab'.symm ▸ e1.2 exact (SimpleGraph.mem_edgeSet h_subdivided_k33).mp hmem have h2' : h_subdivided_k33.Adj c d := by have hmem : Sym2.mk c d ∈ h_subdivided_k33.edgeSet := hcd'.symm ▸ e2.2 exact (SimpleGraph.mem_edgeSet h_subdivided_k33).mp hmem have hv1' : v ∈ s(a, b) := by rwa [← hab'] at hv1 have hv2' : v ∈ s(c, d) := by rwa [← hcd'] at hv2 have hne' : s(a, b) ≠ s(c, d) := by intro h exact hne (Subtype.ext (by rw [← hab', ← hcd']; exact h)) rw [show (e1 : Sym2 (Fin 7)) = s(a, b) from hab'.symm, show (e2 : Sym2 (Fin 7)) = s(c, d) from hcd'.symm, Sym2.lift_mk, Sym2.lift_mk] exact subdivided_k33_line_graph_chromatic_number_eq_four_edge_col_aux a b c d v h1' h2' hv1' hv2' hne'
Two distinct edges sharing a common vertex are adjacent in the line graph.
By definition, two edges are adjacent in the line graph if they are not equal and share a common vertex. Given edges $s(a, b) \neq s(c, d)$ both containing $v$, subtype injectivity (`Subtype.mk.injEq`, `ne_eq`) shows they are distinct as vertices of the line graph, while $v$ witnesses their incidence.
uses
SimpleGraph.mem_edgeSet,ne_eq,Subtype.mk.injEqprivate lemma subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj {V : Type} (G : SimpleGraph V) {a b c d : V} (v : V) (hab : G.Adj a b) (hcd : G.Adj c d) (hne : s(a, b) ≠ s(c, d)) (h1 : v ∈ s(a, b)) (h2 : v ∈ s(c, d)) : G.lineGraph.Adj ⟨s(a, b), (SimpleGraph.mem_edgeSet G).mpr hab⟩ ⟨s(c, d), (SimpleGraph.mem_edgeSet G).mpr hcd⟩ := by refine ⟨?_, ⟨v, h1, h2⟩⟩ simp only [ne_eq, Subtype.mk.injEq] exact hne
No 3-coloring of the 10 edges can satisfy all 19 line-graph adjacency constraints. automation
Given 10 variables in $\mathrm{Fin}\ 3$ representing the colors of the 10 edges, subject to 19 pairwise inequality conditions corresponding to line-graph adjacencies, exhaustive case analysis on the color assignments via `fin_cases` and `simp_all` shows that every branch leads to a contradiction.
private lemma subdivided_k33_line_graph_chromatic_number_eq_four_fin3_no_color (c06 c36 c04 c05 c13 c14 c15 c23 c24 c25 : Fin 3) (h1 : c06 ≠ c04) (h2 : c06 ≠ c05) (h3 : c04 ≠ c05) (h4 : c04 ≠ c14) (h5 : c04 ≠ c24) (h6 : c14 ≠ c24) (h7 : c05 ≠ c15) (h8 : c05 ≠ c25) (h9 : c15 ≠ c25) (h10 : c13 ≠ c14) (h11 : c13 ≠ c15) (h12 : c14 ≠ c15) (h13 : c23 ≠ c24) (h14 : c23 ≠ c25) (h15 : c24 ≠ c25) (h16 : c36 ≠ c13) (h17 : c36 ≠ c23) (h18 : c13 ≠ c23) (h19 : c06 ≠ c36) : False := by fin_cases c06 <;> fin_cases c04 <;> fin_cases c05 <;> simp_all <;> fin_cases c14 <;> simp_all <;> fin_cases c24 <;> simp_all <;> fin_cases c15 <;> simp_all <;> fin_cases c25 <;> simp_all <;> fin_cases c13 <;> simp_all <;> fin_cases c23 <;> simp_all <;> fin_cases c36 <;> simp_all
The line graph of the subdivided $K_{3,3}$ graph is not 3-colorable.
Suppose for contradiction that a proper 3-coloring $C$ exists. We instantiate the 10 edges of `h_subdivided_k33` (verifying their membership using `SimpleGraph.fromRel` and `SimpleGraph.mem_edgeSet`). For each of the 19 incident pairs, line-graph adjacency (`subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj`) implies that their colors under $C$ must differ. Applying `subdivided_k33_line_graph_chromatic_number_eq_four_fin3_no_color` produces `False`.
uses
SimpleGraph.fromRel,SimpleGraph.mem_edgeSet,subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj,subdivided_k33_line_graph_chromatic_number_eq_four_fin3_no_colorprivate lemma subdivided_k33_line_graph_chromatic_number_eq_four_not_colorable_three : ¬ h_subdivided_k33.lineGraph.Colorable 3 := by rintro ⟨C⟩ have h06 : h_subdivided_k33.Adj (0:Fin 7) 6 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h36 : h_subdivided_k33.Adj (3:Fin 7) 6 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h04 : h_subdivided_k33.Adj (0:Fin 7) 4 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h05 : h_subdivided_k33.Adj (0:Fin 7) 5 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h13 : h_subdivided_k33.Adj (1:Fin 7) 3 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h14 : h_subdivided_k33.Adj (1:Fin 7) 4 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h15 : h_subdivided_k33.Adj (1:Fin 7) 5 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h23 : h_subdivided_k33.Adj (2:Fin 7) 3 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h24 : h_subdivided_k33.Adj (2:Fin 7) 4 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h25 : h_subdivided_k33.Adj (2:Fin 7) 5 := by simp [h_subdivided_k33, SimpleGraph.fromRel] let e06 : ↑h_subdivided_k33.edgeSet := ⟨s(0,6), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h06⟩ let e36 : ↑h_subdivided_k33.edgeSet := ⟨s(3,6), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h36⟩ let e04 : ↑h_subdivided_k33.edgeSet := ⟨s(0,4), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h04⟩ let e05 : ↑h_subdivided_k33.edgeSet := ⟨s(0,5), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h05⟩ let e13 : ↑h_subdivided_k33.edgeSet := ⟨s(1,3), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h13⟩ let e14 : ↑h_subdivided_k33.edgeSet := ⟨s(1,4), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h14⟩ let e15 : ↑h_subdivided_k33.edgeSet := ⟨s(1,5), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h15⟩ let e23 : ↑h_subdivided_k33.edgeSet := ⟨s(2,3), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h23⟩ let e24 : ↑h_subdivided_k33.edgeSet := ⟨s(2,4), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h24⟩ let e25 : ↑h_subdivided_k33.edgeSet := ⟨s(2,5), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h25⟩ have c1 : C e06 ≠ C e04 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 0 h06 h04 (by simp) (by simp) (by simp)) have c2 : C e06 ≠ C e05 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 0 h06 h05 (by simp) (by simp) (by simp)) have c3 : C e04 ≠ C e05 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 0 h04 h05 (by simp) (by simp) (by simp)) have c4 : C e04 ≠ C e14 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 4 h04 h14 (by simp) (by simp) (by simp)) have c5 : C e04 ≠ C e24 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 4 h04 h24 (by simp) (by simp) (by simp)) have c6 : C e14 ≠ C e24 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 4 h14 h24 (by simp) (by simp) (by simp)) have c7 : C e05 ≠ C e15 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 5 h05 h15 (by simp) (by simp) (by simp)) have c8 : C e05 ≠ C e25 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 5 h05 h25 (by simp) (by simp) (by simp)) have c9 : C e15 ≠ C e25 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 5 h15 h25 (by simp) (by simp) (by simp)) have c10 : C e13 ≠ C e14 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 1 h13 h14 (by simp) (by simp) (by simp)) have c11 : C e13 ≠ C e15 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 1 h13 h15 (by simp) (by simp) (by simp)) have c12 : C e14 ≠ C e15 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 1 h14 h15 (by simp) (by simp) (by simp)) have c13 : C e23 ≠ C e24 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 2 h23 h24 (by simp) (by simp) (by simp)) have c14 : C e23 ≠ C e25 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 2 h23 h25 (by simp) (by simp) (by simp)) have c15 : C e24 ≠ C e25 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 2 h24 h25 (by simp) (by simp) (by simp)) have c16 : C e36 ≠ C e13 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 3 h36 h13 (by simp) (by simp) (by simp)) have c17 : C e36 ≠ C e23 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 3 h36 h23 (by simp) (by simp) (by simp)) have c18 : C e13 ≠ C e23 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 3 h13 h23 (by simp) (by simp) (by simp)) have c19 : C e06 ≠ C e36 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 6 h06 h36 (by simp) (by simp) (by simp)) exact subdivided_k33_line_graph_chromatic_number_eq_four_fin3_no_color (C e06) (C e36) (C e04) (C e05) (C e13) (C e14) (C e15) (C e23) (C e24) (C e25) c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12 c13 c14 c15 c16 c17 c18 c19
The line graph of the subdivided $K_{3,3}$ graph has chromatic number exactly four.
By `SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable` with $n = 3$, the chromatic number of a graph equals 4 if and only if it is 4-colorable and not 3-colorable. Combining `subdivided_k33_line_graph_chromatic_number_eq_four_colorable_four` and `subdivided_k33_line_graph_chromatic_number_eq_four_not_colorable_three` completes the proof.
uses
SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable,subdivided_k33_line_graph_chromatic_number_eq_four_colorable_four,subdivided_k33_line_graph_chromatic_number_eq_four_not_colorable_threetheorem subdivided_k33_line_graph_chromatic_number_eq_four : h_subdivided_k33.lineGraph.chromaticNumber = 4 := (SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable (G := h_subdivided_k33.lineGraph) (n := 3)).mpr ⟨subdivided_k33_line_graph_chromatic_number_eq_four_colorable_four, subdivided_k33_line_graph_chromatic_number_eq_four_not_colorable_three⟩
SimpleGraph.fromRel- Constructs a simple graph from a symmetric, irreflexive binary relation.
Sym2.mem_iff- An element belongs to an unordered pair if and only if it equals one of the two endpoints: $a \in s(b, c) \leftrightarrow a = b \lor a = c$.
subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne- Distinct edges incident to the same vertex are assigned different colors by the coloring function `gcol`.
subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm- The edge coloring function `gcol` is symmetric in its two arguments: `gcol a b = gcol b a`.
Sym2.eq_swap- An unordered pair is symmetric in its arguments: $s(a, b) = s(b, a)$.
SimpleGraph.Coloring.mk- Constructs a proper graph coloring from a vertex color assignment and a proof that adjacent vertices receive different colors.
Sym2.lift- Lifts a symmetric binary function on $V \times V$ to a well-defined function on unordered pairs $\mathrm{Sym2}(V)$.
Sym2.mk_surjective- Every unordered pair in $\mathrm{Sym2}(\alpha)$ is of the form $s(a, b)$ for some $a, b \in \alpha$.
SimpleGraph.mem_edgeSet- An unordered pair $s(v, w)$ belongs to the edge set of a graph if and only if $v$ and $w$ are adjacent in the graph.
Subtype.ext- Two elements of a subtype are equal if and only if their underlying values are equal.
Sym2.lift_mk- Evaluating the function lifted by `Sym2.lift` on an unordered pair $s(a, b)$ yields the value of the underlying function on $(a, b)$.
subdivided_k33_line_graph_chromatic_number_eq_four_edge_col_aux- Any two distinct edges sharing a vertex receive different colors under `gcol`.
ne_eq- The inequality relation $a \neq b$ is definitionally the negation $\neg (a = b)$.
Subtype.mk.injEq- Two subtype elements are equal if and only if their underlying values are equal.
subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj- Two distinct edges sharing a vertex are adjacent in the line graph.
subdivided_k33_line_graph_chromatic_number_eq_four_fin3_no_color- No assignment of 3 colors to 10 variables can satisfy all 19 pairwise inequality conditions corresponding to the edges of the line graph.
SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable- A graph has chromatic number $n + 1$ if and only if it is $(n + 1)$-colorable and not $n$-colorable.
subdivided_k33_line_graph_chromatic_number_eq_four_colorable_four- The line graph of the subdivided $K_{3,3}$ graph is 4-colorable.
subdivided_k33_line_graph_chromatic_number_eq_four_not_colorable_three- The line graph of the subdivided $K_{3,3}$ graph is not 3-colorable.
- The proof that the line graph is not 3-colorable relies on a brute-force case analysis (`fin_cases`) over the search space of colorings of the 10 edges, rather than a theoretical graph-theoretic obstruction (such as Vizing's theorem or parity arguments on cycles).
- The main theorem on lines 182–185 is stated and proved in term mode rather than tactic mode, directly applying the characterization of chromatic numbers.
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.
Lean’s trace was cut to the first 400 of 654 tactics.
private def subdivided_k33_line_graph_chromatic_number_eq_four_gcol (a b : Fin 7) : Fin 4 := if (a = 0 ∧ b = 6) ∨ (a = 6 ∧ b = 0) then 0 else if (a = 3 ∧ b = 6) ∨ (a = 6 ∧ b = 3) then 3 else if (a = 0 ∧ b = 4) ∨ (a = 4 ∧ b = 0) then 1 else if (a = 0 ∧ b = 5) ∨ (a = 5 ∧ b = 0) then 2 else if (a = 1 ∧ b = 3) ∨ (a = 3 ∧ b = 1) then 2 else if (a = 1 ∧ b = 4) ∨ (a = 4 ∧ b = 1) then 0 else if (a = 1 ∧ b = 5) ∨ (a = 5 ∧ b = 1) then 1 else if (a = 2 ∧ b = 3) ∨ (a = 3 ∧ b = 2) then 1 else if (a = 2 ∧ b = 4) ∨ (a = 4 ∧ b = 2) then 2 else if (a = 2 ∧ b = 5) ∨ (a = 5 ∧ b = 2) then 0 else 0private lemma subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm : ∀ a b : Fin 7, subdivided_k33_line_graph_chromatic_number_eq_four_gcol a b = subdivided_k33_line_graph_chromatic_number_eq_four_gcol b a := by decideprivate lemma subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne : ∀ v x y : Fin 7, h_subdivided_k33.Adj v x → h_subdivided_k33.Adj v y → x ≠ y → subdivided_k33_line_graph_chromatic_number_eq_four_gcol v x ≠ subdivided_k33_line_graph_chromatic_number_eq_four_gcol v y := by have h0 : ∀ x : Fin 7, h_subdivided_k33.Adj (0:Fin 7) x → (x = 6 ∨ x = 4 ∨ x = 5) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h1 : ∀ x : Fin 7, h_subdivided_k33.Adj (1:Fin 7) x → (x = 3 ∨ x = 4 ∨ x = 5) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h2 : ∀ x : Fin 7, h_subdivided_k33.Adj (2:Fin 7) x → (x = 3 ∨ x = 4 ∨ x = 5) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h3 : ∀ x : Fin 7, h_subdivided_k33.Adj (3:Fin 7) x → (x = 6 ∨ x = 1 ∨ x = 2) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h4 : ∀ x : Fin 7, h_subdivided_k33.Adj (4:Fin 7) x → (x = 0 ∨ x = 1 ∨ x = 2) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h5 : ∀ x : Fin 7, h_subdivided_k33.Adj (5:Fin 7) x → (x = 0 ∨ x = 1 ∨ x = 2) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega have h6 : ∀ x : Fin 7, h_subdivided_k33.Adj (6:Fin 7) x → (x = 0 ∨ x = 3) := by intro x hx; simp only [h_subdivided_k33, SimpleGraph.fromRel] at hx; omega intro v x y hx hy hxy fin_cases v · rcases h0 x hx with rfl | rfl | rfl <;> rcases h0 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h1 x hx with rfl | rfl | rfl <;> rcases h1 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h2 x hx with rfl | rfl | rfl <;> rcases h2 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h3 x hx with rfl | rfl | rfl <;> rcases h3 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h4 x hx with rfl | rfl | rfl <;> rcases h4 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h5 x hx with rfl | rfl | rfl <;> rcases h5 y hy with rfl | rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol] · rcases h6 x hx with rfl | rfl <;> rcases h6 y hy with rfl | rfl <;> simp_all [subdivided_k33_line_graph_chromatic_number_eq_four_gcol]private lemma subdivided_k33_line_graph_chromatic_number_eq_four_edge_col_aux : ∀ (a b c d v : Fin 7), h_subdivided_k33.Adj a b → h_subdivided_k33.Adj c d → v ∈ s(a,b) → v ∈ s(c,d) → s(a,b) ≠ s(c,d) → subdivided_k33_line_graph_chromatic_number_eq_four_gcol a b ≠ subdivided_k33_line_graph_chromatic_number_eq_four_gcol c d := by intro a b c d v hab hcd hv1 hv2 hne rw [Sym2.mem_iff] at hv1 hv2 rcases hv1 with hva | hvb · subst v rcases hv2 with hac | had · subst c exact subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne a b d hab hcd (by intro h; exact hne (by rw [h])) · subst d rw [subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm c a] exact subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne a b c hab hcd.symm (by rintro rfl; exact hne Sym2.eq_swap) · subst v rcases hv2 with hbc | hbd · subst c rw [subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm a b] exact subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne b a d hab.symm hcd (by rintro rfl; exact hne Sym2.eq_swap) · subst d rw [subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm a b, subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm c b] exact subdivided_k33_line_graph_chromatic_number_eq_four_gcol_adj_ne b a c hab.symm hcd.symm (by rintro rfl; exact hne rfl)private lemma subdivided_k33_line_graph_chromatic_number_eq_four_colorable_four : h_subdivided_k33.lineGraph.Colorable 4 := by refine ⟨SimpleGraph.Coloring.mk (fun e : ↑h_subdivided_k33.edgeSet => Sym2.lift ⟨subdivided_k33_line_graph_chromatic_number_eq_four_gcol, subdivided_k33_line_graph_chromatic_number_eq_four_gcol_symm⟩ (e : Sym2 (Fin 7))) ?_⟩ intro e1 e2 hAdj obtain ⟨hne, v, hv1, hv2⟩ := hAdj obtain ⟨⟨a, b⟩, hab⟩ := Sym2.mk_surjective (e1 : Sym2 (Fin 7)) obtain ⟨⟨c, d⟩, hcd⟩ := Sym2.mk_surjective (e2 : Sym2 (Fin 7)) have hab' : s(a, b) = (e1 : Sym2 (Fin 7)) := hab have hcd' : s(c, d) = (e2 : Sym2 (Fin 7)) := hcd have h1' : h_subdivided_k33.Adj a b := by have hmem : Sym2.mk a b ∈ h_subdivided_k33.edgeSet := hab'.symm ▸ e1.2 exact (SimpleGraph.mem_edgeSet h_subdivided_k33).mp hmem have h2' : h_subdivided_k33.Adj c d := by have hmem : Sym2.mk c d ∈ h_subdivided_k33.edgeSet := hcd'.symm ▸ e2.2 exact (SimpleGraph.mem_edgeSet h_subdivided_k33).mp hmem have hv1' : v ∈ s(a, b) := by rwa [← hab'] at hv1 have hv2' : v ∈ s(c, d) := by rwa [← hcd'] at hv2 have hne' : s(a, b) ≠ s(c, d) := by intro h exact hne (Subtype.ext (by rw [← hab', ← hcd']; exact h)) rw [show (e1 : Sym2 (Fin 7)) = s(a, b) from hab'.symm, show (e2 : Sym2 (Fin 7)) = s(c, d) from hcd'.symm, Sym2.lift_mk, Sym2.lift_mk] exact subdivided_k33_line_graph_chromatic_number_eq_four_edge_col_aux a b c d v h1' h2' hv1' hv2' hne'private lemma subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj {V : Type} (G : SimpleGraph V) {a b c d : V} (v : V) (hab : G.Adj a b) (hcd : G.Adj c d) (hne : s(a, b) ≠ s(c, d)) (h1 : v ∈ s(a, b)) (h2 : v ∈ s(c, d)) : G.lineGraph.Adj ⟨s(a, b), (SimpleGraph.mem_edgeSet G).mpr hab⟩ ⟨s(c, d), (SimpleGraph.mem_edgeSet G).mpr hcd⟩ := by refine ⟨?_, ⟨v, h1, h2⟩⟩ simp only [ne_eq, Subtype.mk.injEq] exact hneprivate lemma subdivided_k33_line_graph_chromatic_number_eq_four_fin3_no_color (c06 c36 c04 c05 c13 c14 c15 c23 c24 c25 : Fin 3) (h1 : c06 ≠ c04) (h2 : c06 ≠ c05) (h3 : c04 ≠ c05) (h4 : c04 ≠ c14) (h5 : c04 ≠ c24) (h6 : c14 ≠ c24) (h7 : c05 ≠ c15) (h8 : c05 ≠ c25) (h9 : c15 ≠ c25) (h10 : c13 ≠ c14) (h11 : c13 ≠ c15) (h12 : c14 ≠ c15) (h13 : c23 ≠ c24) (h14 : c23 ≠ c25) (h15 : c24 ≠ c25) (h16 : c36 ≠ c13) (h17 : c36 ≠ c23) (h18 : c13 ≠ c23) (h19 : c06 ≠ c36) : False := by fin_cases c06 <;> fin_cases c04 <;> fin_cases c05 <;> simp_all <;> fin_cases c14 <;> simp_all <;> fin_cases c24 <;> simp_all <;> fin_cases c15 <;> simp_all <;> fin_cases c25 <;> simp_all <;> fin_cases c13 <;> simp_all <;> fin_cases c23 <;> simp_all <;> fin_cases c36 <;> simp_allprivate lemma subdivided_k33_line_graph_chromatic_number_eq_four_not_colorable_three : ¬ h_subdivided_k33.lineGraph.Colorable 3 := by rintro ⟨C⟩ have h06 : h_subdivided_k33.Adj (0:Fin 7) 6 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h36 : h_subdivided_k33.Adj (3:Fin 7) 6 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h04 : h_subdivided_k33.Adj (0:Fin 7) 4 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h05 : h_subdivided_k33.Adj (0:Fin 7) 5 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h13 : h_subdivided_k33.Adj (1:Fin 7) 3 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h14 : h_subdivided_k33.Adj (1:Fin 7) 4 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h15 : h_subdivided_k33.Adj (1:Fin 7) 5 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h23 : h_subdivided_k33.Adj (2:Fin 7) 3 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h24 : h_subdivided_k33.Adj (2:Fin 7) 4 := by simp [h_subdivided_k33, SimpleGraph.fromRel] have h25 : h_subdivided_k33.Adj (2:Fin 7) 5 := by simp [h_subdivided_k33, SimpleGraph.fromRel] let e06 : ↑h_subdivided_k33.edgeSet := ⟨s(0,6), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h06⟩ let e36 : ↑h_subdivided_k33.edgeSet := ⟨s(3,6), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h36⟩ let e04 : ↑h_subdivided_k33.edgeSet := ⟨s(0,4), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h04⟩ let e05 : ↑h_subdivided_k33.edgeSet := ⟨s(0,5), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h05⟩ let e13 : ↑h_subdivided_k33.edgeSet := ⟨s(1,3), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h13⟩ let e14 : ↑h_subdivided_k33.edgeSet := ⟨s(1,4), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h14⟩ let e15 : ↑h_subdivided_k33.edgeSet := ⟨s(1,5), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h15⟩ let e23 : ↑h_subdivided_k33.edgeSet := ⟨s(2,3), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h23⟩ let e24 : ↑h_subdivided_k33.edgeSet := ⟨s(2,4), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h24⟩ let e25 : ↑h_subdivided_k33.edgeSet := ⟨s(2,5), (SimpleGraph.mem_edgeSet h_subdivided_k33).mpr h25⟩ have c1 : C e06 ≠ C e04 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 0 h06 h04 (by simp) (by simp) (by simp)) have c2 : C e06 ≠ C e05 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 0 h06 h05 (by simp) (by simp) (by simp)) have c3 : C e04 ≠ C e05 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 0 h04 h05 (by simp) (by simp) (by simp)) have c4 : C e04 ≠ C e14 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 4 h04 h14 (by simp) (by simp) (by simp)) have c5 : C e04 ≠ C e24 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 4 h04 h24 (by simp) (by simp) (by simp)) have c6 : C e14 ≠ C e24 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 4 h14 h24 (by simp) (by simp) (by simp)) have c7 : C e05 ≠ C e15 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 5 h05 h15 (by simp) (by simp) (by simp)) have c8 : C e05 ≠ C e25 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 5 h05 h25 (by simp) (by simp) (by simp)) have c9 : C e15 ≠ C e25 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 5 h15 h25 (by simp) (by simp) (by simp)) have c10 : C e13 ≠ C e14 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 1 h13 h14 (by simp) (by simp) (by simp)) have c11 : C e13 ≠ C e15 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 1 h13 h15 (by simp) (by simp) (by simp)) have c12 : C e14 ≠ C e15 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 1 h14 h15 (by simp) (by simp) (by simp)) have c13 : C e23 ≠ C e24 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 2 h23 h24 (by simp) (by simp) (by simp)) have c14 : C e23 ≠ C e25 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 2 h23 h25 (by simp) (by simp) (by simp)) have c15 : C e24 ≠ C e25 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 2 h24 h25 (by simp) (by simp) (by simp)) have c16 : C e36 ≠ C e13 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 3 h36 h13 (by simp) (by simp) (by simp)) have c17 : C e36 ≠ C e23 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 3 h36 h23 (by simp) (by simp) (by simp)) have c18 : C e13 ≠ C e23 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 3 h13 h23 (by simp) (by simp) (by simp)) have c19 : C e06 ≠ C e36 := C.map_adj (subdivided_k33_line_graph_chromatic_number_eq_four_line_graph_adj h_subdivided_k33 6 h06 h36 (by simp) (by simp) (by simp)) exact subdivided_k33_line_graph_chromatic_number_eq_four_fin3_no_color (C e06) (C e36) (C e04) (C e05) (C e13) (C e14) (C e15) (C e23) (C e24) (C e25) c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12 c13 c14 c15 c16 c17 c18 c19theorem subdivided_k33_line_graph_chromatic_number_eq_four : h_subdivided_k33.lineGraph.chromaticNumber = 4 := (SimpleGraph.chromaticNumber_eq_iff_colorable_not_colorable (G := h_subdivided_k33.lineGraph) (n := 3)).mpr ⟨subdivided_k33_line_graph_chromatic_number_eq_four_colorable_four, subdivided_k33_line_graph_chromatic_number_eq_four_not_colorable_three⟩