third_principal_specialization_card_eq
The third principal specialization of any finite tree on at least one vertex uniquely determines its number of vertices.
Statement
theorem third_principal_specialization_card_eq {V₁ V₂ : Type*} [Fintype V₁] [DecidableEq V₁] [Fintype V₂] [DecidableEq V₂] (T₁ : SimpleGraph V₁) (T₂ : SimpleGraph V₂) [DecidableRel T₁.Adj] [DecidableRel T₂.Adj] (hT₁ : T₁.IsTree) (hT₂ : T₂.IsTree) (heq : third_principal_specialization T₁ = third_principal_specialization T₂) : Fintype.card V₁ = Fintype.card V₂
- Formalizes
- arXiv:2610.31785 Proposition 3.3
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- third_principal_specializationThe third principal specialization of the t-chromatic symmetric function of a graph G is the bivariate polynomial in Z[q, t] given by the…
- third_principal_specialization_eval_oneEvaluating the third principal specialization of a graph G at (1, 1) via MvPolynomial.eval (fun _ => 1) equals the number of proper…
- is_tree_card_coloring_threeFor every finite tree T, the number of proper 3-colorings of T is 3 * 2^(|V| - 1).
- Used by 1
- caterpillar_card_eq_of_third_principal_specialization_eqIf two finite caterpillars have equal third principal specializations, their vertex sets have equal cardinalities.
Read back from the Lean
For any two finite types $V₁$ and $V₂$ with decidable equality, and any simple graphs $T₁$ on $V₁$ and $T₂$ on $V₂$ with decidable adjacency, if both $T₁$ and $T₂$ are trees, and their third principal specializations are equal (third_principal_specialization T₁ = third_principal_specialization T₂), then the number of vertices of $V₁$ is equal to the number of vertices of $V₂$ (Fintype.card V₁ = Fintype.card V₂).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Evaluating the third principal specialization of a graph at (1, 1) counts its proper 3-colorings. For any tree on vertex set V, the number of 3-colorings is 3 * 2 ^ (|V| - 1). Two trees with identical third principal specializations must have identical evaluations at (1, 1), equating 3 * 2 ^ (|V₁| - 1) and 3 * 2 ^ (|V₂| - 1). Canceling 3 and applying injectivity of powers of 2 gives |V₁| - 1 = |V₂| - 1, which implies |V₁| = |V₂| because trees are nonempty.
Evaluating the third principal specialization of each tree at (1, 1) yields 3 * 2 ^ (|V| - 1).
Evaluating the third principal specialization at all ones counts the proper 3-colorings of a graph (third_principal_specialization_eval_one). Because T₁ and T₂ are trees, each has 3 * 2 ^ (|V| - 1) proper 3-colorings (is_tree_card_coloring_three). Rewriting with this formula expresses the evaluation at ones for both trees in terms of their respective vertex counts.
uses
third_principal_specialization_eval_one,is_tree_card_coloring_threehave h₁ := third_principal_specialization_eval_one T₁ have h₂ := third_principal_specialization_eval_one T₂ rw [is_tree_card_coloring_three T₁ hT₁] at h₁ rw [is_tree_card_coloring_three T₂ hT₂] at h₂
3 * 2 ^ (|V₁| - 1) = 3 * 2 ^ (|V₂| - 1) as an equality in ℕ.
Because the third principal specializations of T₁ and T₂ are assumed equal (heq), their evaluations at (1, 1) are equal. Substituting the closed forms from the previous step yields 3 * 2 ^ (|V₁| - 1) = 3 * 2 ^ (|V₂| - 1) in ℤ, which is then cast to an equality of natural numbers using exact_mod_cast.
have hpoly : MvPolynomial.eval (fun _ : Fin 2 => (1:ℤ)) (third_principal_specialization T₁) = MvPolynomial.eval (fun _ : Fin 2 => (1:ℤ)) (third_principal_specialization T₂) := by rw [heq] rw [h₁, h₂] at hpoly have hn : 3 * 2 ^ (Fintype.card V₁ - 1) = 3 * 2 ^ (Fintype.card V₂ - 1) := by exact_mod_cast hpoly
|V₁| - 1 = |V₂| - 1
Canceling the common factor of 3 (via Nat.mul_left_cancel, since 3 > 0) leaves 2 ^ (|V₁| - 1) = 2 ^ (|V₂| - 1). Since the base satisfies 2 ≥ 2, base-2 exponentiation is injective on ℕ (Nat.pow_right_injective), giving |V₁| - 1 = |V₂| - 1.
uses
Nat.mul_left_cancel,Nat.pow_right_injectivehave h2 : 2 ^ (Fintype.card V₁ - 1) = 2 ^ (Fintype.card V₂ - 1) := Nat.mul_left_cancel (by norm_num) hn have hab : Fintype.card V₁ - 1 = Fintype.card V₂ - 1 := Nat.pow_right_injective (by norm_num : 2 ≤ 2) h2
|V₁| = |V₂|
Because trees are connected, their vertex sets are nonempty. A finite type is nonempty if and only if its cardinality is strictly positive (Fintype.card_pos_iff.mpr), which establishes |V₁| > 0 and |V₂| > 0. From |V₁| - 1 = |V₂| - 1 together with positivity of both cardinalities, linear integer arithmetic (omega) concludes that |V₁| = |V₂|.
uses
Fintype.card_pos_iff.mprhave n1 : 0 < Fintype.card V₁ := Fintype.card_pos_iff.mpr hT₁.connected.nonempty have n2 : 0 < Fintype.card V₂ := Fintype.card_pos_iff.mpr hT₂.connected.nonempty omega
third_principal_specialization_eval_one- Evaluating the third principal specialization of a graph with all variables set to 1 equals the number of proper 3-colorings of the graph.
is_tree_card_coloring_three- A finite tree on vertex set V has 3 * 2 ^ (|V| - 1) proper 3-colorings.
Nat.mul_left_cancel- If n > 0 and n * m = n * k in ℕ, then m = k.
Nat.pow_right_injective- For any base a ≥ 2, the power map x ↦ a ^ x is an injective function on ℕ.
Fintype.card_pos_iff.mpr- If a type is nonempty, its cardinality as a finite type is strictly positive.
- In Lean, natural number subtraction is truncated at zero (0 - 1 = 0), so m - 1 = n - 1 only implies m = n when m, n > 0. This necessitates the formal step showing that trees have strictly positive vertex counts before concluding.
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.
/-- The third principal specialization of any tree determines its number of vertices. -/theorem third_principal_specialization_card_eq {V₁ V₂ : Type*} [Fintype V₁] [DecidableEq V₁] [Fintype V₂] [DecidableEq V₂] (T₁ : SimpleGraph V₁) (T₂ : SimpleGraph V₂) [DecidableRel T₁.Adj] [DecidableRel T₂.Adj] (hT₁ : T₁.IsTree) (hT₂ : T₂.IsTree) (heq : third_principal_specialization T₁ = third_principal_specialization T₂) : Fintype.card V₁ = Fintype.card V₂ := by have h₁ := third_principal_specialization_eval_one T₁ have h₂ := third_principal_specialization_eval_one T₂ rw [is_tree_card_coloring_three T₁ hT₁] at h₁ rw [is_tree_card_coloring_three T₂ hT₂] at h₂ have hpoly : MvPolynomial.eval (fun _ : Fin 2 => (1:ℤ)) (third_principal_specialization T₁) = MvPolynomial.eval (fun _ : Fin 2 => (1:ℤ)) (third_principal_specialization T₂) := by rw [heq] rw [h₁, h₂] at hpoly have hn : 3 * 2 ^ (Fintype.card V₁ - 1) = 3 * 2 ^ (Fintype.card V₂ - 1) := by exact_mod_cast hpoly have h2 : 2 ^ (Fintype.card V₁ - 1) = 2 ^ (Fintype.card V₂ - 1) := Nat.mul_left_cancel (by norm_num) hn have hab : Fintype.card V₁ - 1 = Fintype.card V₂ - 1 := Nat.pow_right_injective (by norm_num : 2 ≤ 2) h2 have n1 : 0 < Fintype.card V₁ := Fintype.card_pos_iff.mpr hT₁.connected.nonempty have n2 : 0 < Fintype.card V₂ := Fintype.card_pos_iff.mpr hT₂.connected.nonempty omega