is_tree_card_coloring_three
For every finite tree T, the number of proper 3-colorings of T is 3 * 2^(|V| - 1).
Statement
theorem is_tree_card_coloring_three {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] (hT : T.IsTree) : Fintype.card (T.Coloring (Fin 3)) = 3 * 2 ^ (Fintype.card V - 1)
- Source
- step towards caterpillar_third_t_chromatic_specialization_fiber_le_two
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_tree_induce_compl_singletonRemoving a vertex of degree one from a finite tree yields an induced subgraph that is also a tree.
- is_tree_card_coloring_three_subsingletonA graph on a singleton vertex type has exactly 3 proper 3-colorings.
- is_tree_card_coloring_three_leafRemoving 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).
- Used by 1
- third_principal_specialization_card_eqThe third principal specialization of any finite tree on at least one vertex uniquely determines its number of vertices.
The proof, explained
The theorem is proved by strong induction on the number of vertices n = |V| in an auxiliary lemma. The case n = 0 is impossible because trees are connected and therefore non-empty, while for n = 1 any coloring assigns one of the 3 colors to the single vertex, giving 3 = 3 * 2^0 colorings. For n ≥ 2, every non-trivial finite tree has a leaf v; removing v leaves a tree on n - 1 vertices. Since v has exactly one neighbor, any proper 3-coloring of the smaller tree extends to v in exactly 2 ways, so the number of colorings is 2 * (3 * 2^(n - 2)) = 3 * 2^(n - 1) by the induction hypothesis. The main theorem follows immediately by specializing this result to n = |V|.
Assume the induction hypothesis for trees with fewer than n vertices, and fix an arbitrary tree T on a vertex set V of size n.
We proceed by strong induction on the number of vertices n using Nat.strong_induction_on. In the inductive step, we assume the claim holds for all trees with strictly fewer than n vertices, and introduce an arbitrary finite vertex type V of cardinality n together with a tree T on V.
uses
Nat.strong_induction_onintro n induction n using Nat.strong_induction_on with | h n ih => intro V _ _ T _ hcard hT
The case n = 0 is impossible because trees are non-empty.
By definition, a tree is connected, so its vertex set V is non-empty. A non-empty finite set has cardinality at least 1 (Fintype.card_pos_iff.mpr), which contradicts the assumption that n = |V| = 0. Linear arithmetic (omega) closes the goal from this contradiction.
uses
Fintype.card_pos_iff.mprcases n with | zero => exfalso have hne : Nonempty V := hT.connected.nonempty have hpos : 0 < Fintype.card V := Fintype.card_pos_iff.mpr hne omega
When n = 1, the tree has 3 = 3 * 2^(1 - 1) proper 3-colorings.
When n = 1, the vertex set V has cardinality 1, so it is both a subsingleton (Fintype.card_le_one_iff_subsingleton.mp) and non-empty. By is_tree_card_coloring_three_subsingleton, any tree on a single vertex has exactly 3 proper 3-colorings. Simplification (simp) verifies that 3 = 3 * 2^(1 - 1).
uses
Fintype.card_le_one_iff_subsingleton.mp,is_tree_card_coloring_three_subsingleton| succ m => cases m with | zero => haveI : Subsingleton V := Fintype.card_le_one_iff_subsingleton.mp (by omega) haveI : Nonempty V := hT.connected.nonempty rw [is_tree_card_coloring_three_subsingleton T] simpWhen n = k + 2 ≥ 2, there exists a leaf v whose removal leaves a tree on k + 1 vertices and halves the coloring count.
Since |V| = k + 2 ≥ 2, V is non-trivial (nontrivial_iff, Fintype.one_lt_card_iff.mp). Every non-trivial finite tree has a leaf v (a vertex of degree 1). By is_tree_card_coloring_three_leaf, proper 3-colorings of T correspond to proper 3-colorings of the induced subgraph on V \ {v} with 2 independent choices for the color of v. Moreover, removing a leaf leaves an induced subgraph that is still a tree (is_tree_induce_compl_singleton).
uses
nontrivial_iff,Fintype.one_lt_card_iff.mp,is_tree_card_coloring_three_leaf,is_tree_induce_compl_singleton| succ k => haveI : Nontrivial V := by rw [nontrivial_iff] exact Fintype.one_lt_card_iff.mp (by omega) obtain ⟨v, hv⟩ := hT.exists_vert_degree_one_of_nontrivial rw [is_tree_card_coloring_three_leaf T hv] have hT' : (T.induce (({v} : Set V)ᶜ)).IsTree := is_tree_induce_compl_singleton T hT hvBy the induction hypothesis, T \ {v} has 3 * 2^k proper 3-colorings, so T has 3 * 2^(n - 1) colorings.
The vertex set V \ {v} has cardinality |V| - 1 = k + 1 by Fintype.card_subtype_compl. Since k + 1 < n, the induction hypothesis applies to T \ {v}, giving 3 * 2^k colorings. Multiplying by 2 gives 2 * (3 * 2^k) = 3 * 2^(k + 1), which equals 3 * 2^(n - 1) by ring arithmetic.
uses
Fintype.card_subtype_complhave hcard' : Fintype.card ↥(({v} : Set V)ᶜ) = k + 1 := by have h1 : Fintype.card ↥(({v} : Set V)ᶜ) = Fintype.card V - Fintype.card {x : V // x ∈ ({v} : Set V)} := by show Fintype.card {x : V // ¬ x ∈ ({v} : Set V)} = _ exact Fintype.card_subtype_compl (fun x : V => x ∈ ({v} : Set V)) rw [h1] simp omega have hih := ih (k + 1) (by omega) ↥(({v} : Set V)ᶜ) (T.induce (({v} : Set V)ᶜ)) hcard' hT' rw [hih] have e : k + 1 - 1 = k := by omega rw [e] have e2 : k + 1 + 1 - 1 = k + 1 := by omega rw [e2] ring
For every finite tree T, the number of proper 3-colorings is 3 * 2^(|V| - 1).
We apply the auxiliary lemma is_tree_card_coloring_three_aux with n = |V|, using the reflexivity of equality |V| = |V| and the assumption that T is a tree.
uses
is_tree_card_coloring_three_auxexact is_tree_card_coloring_three_aux (Fintype.card V) V T rfl hT
Nat.strong_induction_on- Principle of strong (well-founded) induction on the natural numbers.
Fintype.card_pos_iff.mpr- A finite type has strictly positive cardinality if and only if it is non-empty.
Fintype.card_le_one_iff_subsingleton.mp- A finite type with at most one element is a subsingleton.
is_tree_card_coloring_three_subsingleton- A non-empty tree on a single vertex has exactly 3 proper 3-colorings.
nontrivial_iff- A type is nontrivial if and only if it has two distinct elements.
Fintype.one_lt_card_iff.mp- A finite type has more than one element if and only if there exist two distinct elements.
is_tree_card_coloring_three_leaf- For any leaf v of a graph T, the number of 3-colorings of T is twice the number of 3-colorings of T with v removed.
is_tree_induce_compl_singleton- Removing a leaf from a tree leaves an induced subgraph that is still a tree.
Fintype.card_subtype_compl- The cardinality of the subtype of elements not satisfying a predicate is the total cardinality minus the cardinality of the subtype satisfying the predicate.
is_tree_card_coloring_three_aux- Auxiliary lemma stating that any tree on n vertices has 3 * 2^(n - 1) proper 3-colorings.
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.
private lemma is_tree_card_coloring_three_aux.{u} : ∀ (n : Nat) (V : Type u) [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj], Fintype.card V = n → T.IsTree → Fintype.card (T.Coloring (Fin 3)) = 3 * 2 ^ (n - 1) := by intro n induction n using Nat.strong_induction_on with | h n ih => intro V _ _ T _ hcard hT cases n with | zero => exfalso have hne : Nonempty V := hT.connected.nonempty have hpos : 0 < Fintype.card V := Fintype.card_pos_iff.mpr hne omega | succ m => cases m with | zero => haveI : Subsingleton V := Fintype.card_le_one_iff_subsingleton.mp (by omega) haveI : Nonempty V := hT.connected.nonempty rw [is_tree_card_coloring_three_subsingleton T] simp | succ k => haveI : Nontrivial V := by rw [nontrivial_iff] exact Fintype.one_lt_card_iff.mp (by omega) obtain ⟨v, hv⟩ := hT.exists_vert_degree_one_of_nontrivial rw [is_tree_card_coloring_three_leaf T hv] have hT' : (T.induce (({v} : Set V)ᶜ)).IsTree := is_tree_induce_compl_singleton T hT hv have hcard' : Fintype.card ↥(({v} : Set V)ᶜ) = k + 1 := by have h1 : Fintype.card ↥(({v} : Set V)ᶜ) = Fintype.card V - Fintype.card {x : V // x ∈ ({v} : Set V)} := by show Fintype.card {x : V // ¬ x ∈ ({v} : Set V)} = _ exact Fintype.card_subtype_compl (fun x : V => x ∈ ({v} : Set V)) rw [h1] simp omega have hih := ih (k + 1) (by omega) ↥(({v} : Set V)ᶜ) (T.induce (({v} : Set V)ᶜ)) hcard' hT' rw [hih] have e : k + 1 - 1 = k := by omega rw [e] have e2 : k + 1 + 1 - 1 = k + 1 := by omega rw [e2] ring/-- For every finite tree T, the number of proper 3-colorings is 3 * 2^(|V| - 1). -/theorem is_tree_card_coloring_three {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] (hT : T.IsTree) : Fintype.card (T.Coloring (Fin 3)) = 3 * 2 ^ (Fintype.card V - 1) := by exact is_tree_card_coloring_three_aux (Fintype.card V) V T rfl hT