AFTD Auto-Formalizing Theoretical Domains

is_tree_card_coloring_three

theoremverified

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
Used by 1

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

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

    lines 5–8

    uses Nat.strong_induction_on

      intro n
      induction n using Nat.strong_induction_on with
      | h n ih =>
        intro V _ _ T _ hcard hT
  2. 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.

    lines 9–14

    uses Fintype.card_pos_iff.mpr

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

    lines 15–21

    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]
                simp
  4. When 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).

    lines 22–29

    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 hv
  5. By 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.

    lines 30–45

    uses Fintype.card_subtype_compl

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

    line 51

    uses is_tree_card_coloring_three_aux

      exact 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

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