simple_graph_t_chromatic_ps_vertex_count_eq
Let n ≥ 2 and let G be a finite simple graph with at least 2 vertices that has a proper coloring with n colors (χ_G(n) > 0). Let d and D be the minimum and maximum degrees of q appearing in the n-th principal specialization ps_n(Z_G(x; t)) (the least and greatest j such that the coefficient of t^k q^j is nonzero for some k). Then the number of vertices of G equals (d + D)/(n - 1), computed in ℚ.
Statement
theorem simple_graph_t_chromatic_ps_vertex_count_eq {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 2 ≤ n) (hV : 2 ≤ Fintype.card V) (hcol : G.Colorable n) (d D : ℕ) (hd : IsLeast {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} d) (hD : IsGreatest {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} D) : (Fintype.card V : ℚ) = ((d : ℚ) + D) / ((n : ℚ) - 1)
- Formalizes
- arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16(1)
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_t_chromatic_principal_specializationFor a finite simple graph G on a finite vertex type V and a natural number n, the n-th principal specialization of the t-chromatic…
- simple_graph_t_chromatic_ps_min_add_max_q_degreeFor a finite simple graph G and n ∈ ℕ, if d and D are the least and greatest exponents j of q such that some coefficient of t^k q^j in…
Read back from the Lean
For any finite type $V$, any simple graph $G$ on $V$, any natural number $n$, and any natural numbers $d$ and $D$, assuming:
1. $2 \le n$,
2. $2 \le |V|$,
3. $G$ is $n$-colorable (G.Colorable n),
4. $d$ is the least element of the set of natural numbers $j$ such that there exists $k \in \mathbb{N}$ for which the $j$-th coefficient of the $k$-th coefficient of simple_graph_t_chromatic_principal_specialization G n is non-zero (IsLeast {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} d), and
5. $D$ is the greatest element of that same set (IsGreatest ... D),
the cardinality of $V$ (cast to $\mathbb{Q}$) is equal to $\frac{d + D}{n - 1}$.
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
The proof derives the rational expression for the vertex count |V| = (d + D) / (n - 1) from the known natural number identity (n - 1) * |V| = d + D. Because n ≥ 2, the denominator n - 1 is nonzero, so clearing the division reduces the goal to |V| * (n - 1) = d + D. Casting the natural number identity to ℚ and commuting the factors finishes the argument.
The integer identity (n - 1) * |V| = d + D holds.
We invoke the existing theorem simple_graph_t_chromatic_ps_min_add_max_q_degree, which relates the number of vertices |V| to the sum of the minimum and maximum q-degrees d and D in the principal specialization.
uses
simple_graph_t_chromatic_ps_min_add_max_q_degreehave h := simple_graph_t_chromatic_ps_min_add_max_q_degree G n d D hd hDThe denominator (n : ℚ) - 1 is nonzero.
Since n ≥ 2, casting to ℚ gives n ≥ 2, and linear arithmetic shows n - 1 ≥ 1 > 0, so n - 1 ≠ 0.
have hn' : ((n : ℚ) - 1) ≠ 0 := by have : (2 : ℚ) ≤ n := by exact_mod_cast hn linarith
It suffices to prove |V| * (n - 1) = d + D in ℚ.
Because n - 1 ≠ 0, we can rewrite the rational division |V| = (d + D) / (n - 1) into the equivalent multiplicative form |V| * (n - 1) = d + D using eq_div_iff.
uses
eq_div_iffrw [eq_div_iff hn']The equality |V| * (n - 1) = d + D holds in ℚ, concluding the proof.
We cast the integer equation (n - 1) * |V| = d + D to ℚ. Since 1 ≤ n holds by linear arithmetic (via omega from n ≥ 2), Nat.cast_sub allows expanding the cast of n - 1 into (n : ℚ) - 1. Pushing the casts produces (n - 1) * |V| = d + D in ℚ, from which linear arithmetic closes the goal by commutativity of multiplication.
uses
Nat.cast_subhave h' : ((n - 1 : ℕ) : ℚ) * (Fintype.card V : ℚ) = (d : ℚ) + D := by exact_mod_cast h rw [Nat.cast_sub (by omega)] at h' push_cast at h' linarith
simple_graph_t_chromatic_ps_min_add_max_q_degree- For a finite graph G and integer n, the sum of the minimum degree d and maximum degree D of q in the n-th principal specialization equals (n - 1) |V|.
eq_div_iff- In a division ring or field, given a nonzero denominator b ≠ 0, c = a / b holds if and only if c * b = a.
Nat.cast_sub- For natural numbers m ≤ n, casting n - m to an additive group with one equals the difference of the casts, ↑n - ↑m.
- The hypotheses that the graph has at least two vertices (hV) and is n-colorable (hcol) are included in the theorem statement but are not directly used in the proof, as the identity (n - 1)|V| = d + D was already proved separately.
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.
theorem simple_graph_t_chromatic_ps_vertex_count_eq {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 2 ≤ n) (hV : 2 ≤ Fintype.card V) (hcol : G.Colorable n) (d D : ℕ) (hd : IsLeast {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} d) (hD : IsGreatest {j | ∃ k, ((simple_graph_t_chromatic_principal_specialization G n).coeff k).coeff j ≠ 0} D) : (Fintype.card V : ℚ) = ((d : ℚ) + D) / ((n : ℚ) - 1) := by have h := simple_graph_t_chromatic_ps_min_add_max_q_degree G n d D hd hD have hn' : ((n : ℚ) - 1) ≠ 0 := by have : (2 : ℚ) ≤ n := by exact_mod_cast hn linarith rw [eq_div_iff hn'] have h' : ((n - 1 : ℕ) : ℚ) * (Fintype.card V : ℚ) = (d : ℚ) + D := by exact_mod_cast h rw [Nat.cast_sub (by omega)] at h' push_cast at h' linarith