AFTD Auto-Formalizing Theoretical Domains

is_tree_card_coloring_three_leaf

theoremverified

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

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

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

    lines 5–9

    uses SimpleGraph.degree_eq_one_iff_existsUnique_adj, SimpleGraph.ne_of_adj, Set.mem_compl_iff, Set.mem_singleton_iff

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

    lines 10–40

    uses SimpleGraph.Coloring.mk, dif_neg, dif_pos, Set.mem_compl_iff, Set.mem_singleton_iff, not_not.mp, Subtype.ext

      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])
  3. 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).

    lines 41–54

    uses RelHom.ext, dif_pos, dif_neg, Set.mem_compl_iff, Set.mem_singleton_iff, not_not.mp

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

    lines 55–65

    uses RelHom.ext, dif_pos, dif_neg, Subtype.ext, Prod.ext

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

    lines 66–73

    uses Equiv.ofBijective

      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 }
  6. 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.

    lines 74–76

      have h2c : ∀ x : Fin 3, Fintype.card {a : Fin 3 // a ≠ x} = 2 := by
        intro x
        fin_cases x <;> decide
  7. 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)|.

    lines 77–81

    uses Fintype.card_congr, Fintype.card_sigma, Finset.sum_const, Finset.card_univ, Nat.mul_comm

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

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

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