is_tree_card_coloring_three_leaf
Removing a leaf of degree 1 from a graph halves the number of proper 3-colorings (each coloring of T \ {v} extends in exactly 2 ways to v).
Statement
lemma is_tree_card_coloring_three_leaf {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] {v : V} (hv : T.degree v = 1) : Fintype.card (T.Coloring (Fin 3)) = 2 * Fintype.card ((T.induce {v}ᶜ).Coloring (Fin 3))
- Source
- step towards is_tree_card_coloring_three
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- is_tree_card_coloring_threeFor every finite tree T, the number of proper 3-colorings of T is 3 * 2^(|V| - 1).
The proof, explained
To count the proper 3-colorings of a graph T with a leaf v of degree 1, the proof constructs an explicit bijection between colorings of T and pairs (C', c), where C' is a proper 3-coloring of T \ {v} and c ∈ {0, 1, 2} is a color for v distinct from the color of its unique neighbor u. This pair type is then represented as a dependent sum over colorings C' whose fibers are the sets of valid colors for v. Because u has already received a color, there are always exactly 3 - 1 = 2 choices for v, so summing this constant fiber size over all colorings of T \ {v} shows that the number of colorings of T is exactly twice the number of colorings of T \ {v}.
The leaf v has a unique neighbor u, and u is distinct from v (u ∈ {v}ᶜ).
Since v has degree 1, SimpleGraph.degree_eq_one_iff_existsUnique_adj provides a unique neighbor u adjacent to v. Because an edge connects distinct vertices in a simple graph (SimpleGraph.ne_of_adj), u ≠ v, which by Set.mem_compl_iff and Set.mem_singleton_iff means u lies in the complement of {v}.
uses
SimpleGraph.degree_eq_one_iff_existsUnique_adj,SimpleGraph.ne_of_adj,Set.mem_compl_iff,Set.mem_singleton_iffclassical obtain ⟨u, huv, huniq⟩ := (SimpleGraph.degree_eq_one_iff_existsUnique_adj).mp hv have humem : u ∈ ({v}ᶜ : Set V) := by simp only [Set.mem_compl_iff, Set.mem_singleton_iff] exact (SimpleGraph.ne_of_adj T huv).symm
Define the restriction of colorings, the subtype Aty of pairs (C', c) with c ≠ C'(u), and the extension map g : Aty → T.Coloring (Fin 3).
Any coloring on T restricts to the induced subgraph on V \ {v}. We define Aty as the type of pairs (C', c) of a 3-coloring C' of T \ {v} and a color c ∈ Fin 3 such that c ≠ C'(u). The function g extends such a pair by assigning color c to v and C'(w) to any w ≠ v. To prove this extension is a valid coloring (SimpleGraph.Coloring.mk), we check edge pairs x ~ y: if x = v, uniqueness of the neighbor of v forces y = u, so the colors are c and C'(u), which are distinct by the definition of Aty; if x, y ≠ v, the colors differ because C' is valid; and if y = v, symmetry similarly forces x = u.
uses
SimpleGraph.Coloring.mk,dif_neg,dif_pos,Set.mem_compl_iff,Set.mem_singleton_iff,not_not.mp,Subtype.extlet restr : T.Coloring (Fin 3) → (T.induce {v}ᶜ).Coloring (Fin 3) := fun C => SimpleGraph.Coloring.mk (fun (x : ↥({v}ᶜ : Set V)) => C x.val) (fun {x y} h => C.valid h) let Aty := {p : ((T.induce {v}ᶜ).Coloring (Fin 3)) × Fin 3 // p.2 ≠ p.1 ⟨u, humem⟩} let g : Aty → T.Coloring (Fin 3) := fun p => SimpleGraph.Coloring.mk (fun w : V => if h : w ∈ ({v}ᶜ : Set V) then p.1.1 ⟨w, h⟩ else p.1.2) (fun {x y} hxy => by by_cases hxv : x = v · subst hxv have hyu : y = u := huniq y hxy subst hyu rw [dif_neg (by simp), dif_pos humem] exact p.2 · by_cases hy : y ∈ ({v}ᶜ : Set V) · rw [dif_pos (by simpa using hxv), dif_pos hy] exact p.1.1.valid hxy · rw [dif_pos (by simpa using hxv), dif_neg hy] have hyv : y = v := by simp only [Set.mem_compl_iff, Set.mem_singleton_iff] at hy exact not_not.mp hy have hxu : x = u := by refine huniq x ?_ rw [← hyv] exact hxy.symm intro hcontra refine p.2 ?_ calc p.1.2 = p.1.1 ⟨x, by simpa using hxv⟩ := hcontra.symm _ = p.1.1 ⟨u, humem⟩ := by rw [show (⟨x, by simpa using hxv⟩ : ↥({v}ᶜ : Set V)) = ⟨u, humem⟩ from Subtype.ext hxu])
The restriction map f : C ↦ (C|_{V \ {v}}, C(v)) lands in Aty, and g is a left inverse of f (g ∘ f = id).
For any coloring C of T, the adjacency v ~ u guarantees C(v) ≠ C(u), so (C|_{V \ {v}}, C(v)) satisfies the condition for Aty. To show g(f(C)) = C, by RelHom.ext it suffices to check vertex-by-vertex: if w ≠ v, g(f(C))(w) evaluates to C(w) from the restriction, and if w = v, it evaluates to C(v).
uses
RelHom.ext,dif_pos,dif_neg,Set.mem_compl_iff,Set.mem_singleton_iff,not_not.mplet f : T.Coloring (Fin 3) → Aty := fun C => ⟨(restr C, C v), C.valid huv⟩ have hleft : Function.LeftInverse g f := by intro C apply RelHom.ext intro w show (if h : w ∈ ({v}ᶜ : Set V) then (restr C) ⟨w, h⟩ else C v) = C w by_cases hw : w ∈ ({v}ᶜ : Set V) · rw [dif_pos hw] rfl · rw [dif_neg hw] have hwv : w = v := by simp only [Set.mem_compl_iff, Set.mem_singleton_iff] at hw exact not_not.mp hw rw [hwv]
g is a right inverse of f (f ∘ g = id).
For any p = (C', c) ∈ Aty, the restriction of g(p) to V \ {v} recovers C' because g(p) agrees with C' off v (proven via RelHom.ext), and g(p)(v) = c by definition. Using Subtype.ext and Prod.ext, this shows f(g(p)) = p.
uses
RelHom.ext,dif_pos,dif_neg,Subtype.ext,Prod.exthave hright : Function.RightInverse g f := by intro p have h1 : restr (g p) = p.1.1 := by apply RelHom.ext intro w show (if h : w.1 ∈ ({v}ᶜ : Set V) then p.1.1 ⟨w.1, h⟩ else p.1.2) = p.1.1 w rw [dif_pos w.2] have h2 : (g p) v = p.1.2 := by show (if h : v ∈ ({v}ᶜ : Set V) then p.1.1 ⟨v, h⟩ else p.1.2) = p.1.2 rw [dif_neg (by simp)] exact Subtype.ext (Prod.ext h1 h2)
There are bijections T.Coloring (Fin 3) ≃ Aty and Aty ≃ Σ C', {c : Fin 3 // c ≠ C'(u)}.
Having shown that g is both a left and right inverse to f, Equiv.ofBijective establishes an equivalence e1 between colorings of T and Aty. The second equivalence e2 reinterprets the subtype Aty of pairs as a dependent sum (sigma type) over colorings C' of the leaf-deleted graph, where the fiber over C' consists of all colors distinct from C'(u).
uses
Equiv.ofBijectivehave e1 : T.Coloring (Fin 3) ≃ Aty := Equiv.ofBijective f ⟨hleft.injective, hright.surjective⟩ have e2 : Aty ≃ (Σ r : (T.induce {v}ᶜ).Coloring (Fin 3), {a : Fin 3 // a ≠ r ⟨u, humem⟩}) := { toFun := fun p => ⟨p.1.1, ⟨p.1.2, p.2⟩⟩ invFun := fun s => ⟨(s.1, s.2.val), s.2.property⟩ left_inv := fun p => rfl right_inv := fun s => rfl }
For any color x ∈ Fin 3, exactly 2 colors in Fin 3 differ from x.
Case analysis on the three values of x ∈ Fin 3 (via fin_cases) followed by exhaustive evaluation (decide) verifies that the subtype of colors unequal to x has cardinality 2 in each case.
have h2c : ∀ x : Fin 3, Fintype.card {a : Fin 3 // a ≠ x} = 2 := by intro x fin_cases x <;> decide
The number of 3-colorings of T is twice the number of 3-colorings of T \ {v}.
Rewriting the cardinality of T.Coloring (Fin 3) along the bijections e1 and e2 via Fintype.card_congr and applying Fintype.card_sigma gives the sum over all colorings C' of T \ {v} of the fiber sizes |{c // c ≠ C'(u)}|. Since each fiber has cardinality 2, Finset.sum_const and Finset.card_univ evaluate the sum to |(T \ {v}).Coloring (Fin 3)| * 2. Applying Nat.mul_comm concludes that this equals 2 * |(T \ {v}).Coloring (Fin 3)|.
uses
Fintype.card_congr,Fintype.card_sigma,Finset.sum_const,Finset.card_univ,Nat.mul_commrw [Fintype.card_congr e1, Fintype.card_congr e2, Fintype.card_sigma] simp only [h2c, Finset.sum_const, Finset.card_univ] show Fintype.card ((T.induce {v}ᶜ).Coloring (Fin 3)) * 2 = 2 * Fintype.card ((T.induce {v}ᶜ).Coloring (Fin 3)) exact Nat.mul_comm _ _
SimpleGraph.degree_eq_one_iff_existsUnique_adj- A vertex in a simple graph has degree 1 if and only if there exists a unique vertex adjacent to it.
SimpleGraph.ne_of_adj- In a simple graph, two adjacent vertices are distinct.
Set.mem_compl_iff- An element belongs to the complement of a set if and only if it does not belong to the set.
Set.mem_singleton_iff- An element belongs to a singleton set {b} if and only if it equals b.
SimpleGraph.Coloring.mk- Constructs a valid graph coloring from a vertex map and a proof that adjacent vertices receive different colors.
dif_neg- A dependent if-then-else expression evaluates to its else branch when the condition is false.
dif_pos- A dependent if-then-else expression evaluates to its then branch when the condition is true.
not_not.mp- Double negation elimination: if not not p holds, then p holds.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
RelHom.ext- Two relation homomorphisms (such as graph colorings) are equal if they agree on all vertices.
Prod.ext- Two pairs are equal if their first and second components are respectively equal.
Equiv.ofBijective- A bijective function induces an equivalence (bijection) between its domain and codomain.
Fintype.card_congr- Equivalent finite types have the same cardinality.
Fintype.card_sigma- The cardinality of a dependent sum (sigma type) is the sum of the cardinalities of its fibers.
Finset.sum_const- Summing a constant value over a finite set equals the cardinality of the set times the constant.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
- While the paper proof straightforwardly multiplies by 2 because a leaf has one neighbor and thus two available colors, the Lean formalization requires explicitly constructing the extension and restriction maps, proving that extending a coloring preserves properness on all edges, showing they form a two-sided inverse, and converting the subtype of pairs into a dependent sum over colorings to apply the summation lemma.
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.
/-- Removing a leaf of degree 1 from a graph halves the number of proper 3-colorings (each coloring of T \ {v} extends in exactly 2 ways to v). -/lemma is_tree_card_coloring_three_leaf {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] {v : V} (hv : T.degree v = 1) : Fintype.card (T.Coloring (Fin 3)) = 2 * Fintype.card ((T.induce {v}ᶜ).Coloring (Fin 3)) := by classical obtain ⟨u, huv, huniq⟩ := (SimpleGraph.degree_eq_one_iff_existsUnique_adj).mp hv have humem : u ∈ ({v}ᶜ : Set V) := by simp only [Set.mem_compl_iff, Set.mem_singleton_iff] exact (SimpleGraph.ne_of_adj T huv).symm let restr : T.Coloring (Fin 3) → (T.induce {v}ᶜ).Coloring (Fin 3) := fun C => SimpleGraph.Coloring.mk (fun (x : ↥({v}ᶜ : Set V)) => C x.val) (fun {x y} h => C.valid h) let Aty := {p : ((T.induce {v}ᶜ).Coloring (Fin 3)) × Fin 3 // p.2 ≠ p.1 ⟨u, humem⟩} let g : Aty → T.Coloring (Fin 3) := fun p => SimpleGraph.Coloring.mk (fun w : V => if h : w ∈ ({v}ᶜ : Set V) then p.1.1 ⟨w, h⟩ else p.1.2) (fun {x y} hxy => by by_cases hxv : x = v · subst hxv have hyu : y = u := huniq y hxy subst hyu rw [dif_neg (by simp), dif_pos humem] exact p.2 · by_cases hy : y ∈ ({v}ᶜ : Set V) · rw [dif_pos (by simpa using hxv), dif_pos hy] exact p.1.1.valid hxy · rw [dif_pos (by simpa using hxv), dif_neg hy] have hyv : y = v := by simp only [Set.mem_compl_iff, Set.mem_singleton_iff] at hy exact not_not.mp hy have hxu : x = u := by refine huniq x ?_ rw [← hyv] exact hxy.symm intro hcontra refine p.2 ?_ calc p.1.2 = p.1.1 ⟨x, by simpa using hxv⟩ := hcontra.symm _ = p.1.1 ⟨u, humem⟩ := by rw [show (⟨x, by simpa using hxv⟩ : ↥({v}ᶜ : Set V)) = ⟨u, humem⟩ from Subtype.ext hxu]) let f : T.Coloring (Fin 3) → Aty := fun C => ⟨(restr C, C v), C.valid huv⟩ have hleft : Function.LeftInverse g f := by intro C apply RelHom.ext intro w show (if h : w ∈ ({v}ᶜ : Set V) then (restr C) ⟨w, h⟩ else C v) = C w by_cases hw : w ∈ ({v}ᶜ : Set V) · rw [dif_pos hw] rfl · rw [dif_neg hw] have hwv : w = v := by simp only [Set.mem_compl_iff, Set.mem_singleton_iff] at hw exact not_not.mp hw rw [hwv] have hright : Function.RightInverse g f := by intro p have h1 : restr (g p) = p.1.1 := by apply RelHom.ext intro w show (if h : w.1 ∈ ({v}ᶜ : Set V) then p.1.1 ⟨w.1, h⟩ else p.1.2) = p.1.1 w rw [dif_pos w.2] have h2 : (g p) v = p.1.2 := by show (if h : v ∈ ({v}ᶜ : Set V) then p.1.1 ⟨v, h⟩ else p.1.2) = p.1.2 rw [dif_neg (by simp)] exact Subtype.ext (Prod.ext h1 h2) have e1 : T.Coloring (Fin 3) ≃ Aty := Equiv.ofBijective f ⟨hleft.injective, hright.surjective⟩ have e2 : Aty ≃ (Σ r : (T.induce {v}ᶜ).Coloring (Fin 3), {a : Fin 3 // a ≠ r ⟨u, humem⟩}) := { toFun := fun p => ⟨p.1.1, ⟨p.1.2, p.2⟩⟩ invFun := fun s => ⟨(s.1, s.2.val), s.2.property⟩ left_inv := fun p => rfl right_inv := fun s => rfl } have h2c : ∀ x : Fin 3, Fintype.card {a : Fin 3 // a ≠ x} = 2 := by intro x fin_cases x <;> decide rw [Fintype.card_congr e1, Fintype.card_congr e2, Fintype.card_sigma] simp only [h2c, Finset.sum_const, Finset.card_univ] show Fintype.card ((T.induce {v}ᶜ).Coloring (Fin 3)) * 2 = 2 * Fintype.card ((T.induce {v}ᶜ).Coloring (Fin 3)) exact Nat.mul_comm _ _