AFTD Auto-Formalizing Theoretical Domains

simple_graph_t_chromatic_ps_vertex_count_eq

theoremverifiedformalization

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

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.

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

    line 6

    uses simple_graph_t_chromatic_ps_min_add_max_q_degree

      have h := simple_graph_t_chromatic_ps_min_add_max_q_degree G n d D hd hD
  2. The 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.

    lines 7–9

      have hn' : ((n : ℚ) - 1) ≠ 0 := by
        have : (2 : ℚ) ≤ n := by exact_mod_cast hn
        linarith
  3. 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.

    line 10

    uses eq_div_iff

      rw [eq_div_iff hn']
  4. 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.

    lines 11–14

    uses Nat.cast_sub

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

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

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