AFTD Auto-Formalizing Theoretical Domains

simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite

theoremverifiedformalization

Let n ≥ 2 and let G be a connected finite simple graph with at least 2 vertices that has a proper coloring with n colors, and let b : V → Fin 2 be a proper 2-coloring of G (so G is bipartite). Let c1 and c2 be the smaller and the larger of the sizes of the two parts {v | b v = 0} and {v | b v = 1}. Then the coefficient of t^2 in ps_n(Z_G(x; t)) equals the sum over ordered pairs (j1, j2) of distinct elements of {0, ..., n-1} of q^(c1 j1 + c2 j2).

Statement

theorem simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 2 ≤ n)
    (hV : 2 ≤ Fintype.card V) (hcol : G.Colorable n) (hconn : G.Connected)
    (b : G.Coloring (Fin 2)) :
    (simple_graph_t_chromatic_principal_specialization G n).coeff 2 =
      ∑ p ∈ Finset.univ.filter (fun p : Fin n × Fin n => p.1 ≠ p.2),
        Polynomial.X ^ (min (Finset.univ.filter (fun v => b v = 0)).card
                            (Finset.univ.filter (fun v => b v = 1)).card * (p.1 : ℕ) +
                        max (Finset.univ.filter (fun v => b v = 0)).card
                            (Finset.univ.filter (fun v => b v = 1)).card * (p.2 : ℕ))
Formalizes
arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16(3); the bipartition is given as a proper 2-coloring b, whose parts are the unique bipartition of the connected graph
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

Read back from the Lean

Let $V$ be a finite type, and let $G$ be a simple graph on $V$. Let $n$ be a natural number such that $2 \le n$. Assume that $V$ has at least 2 vertices, that $G$ is $n$-colorable, that $G$ is connected, and let $b$ be a proper 2-coloring of $G$ with colors in $\operatorname{Fin} 2$. Then the coefficient at degree 2 of the principal specialization of the $t$-chromatic polynomial of $G$ with $n$ colors, simple_graph_t_chromatic_principal_specialization G n, is equal to the sum over all pairs $(p_1, p_2) \in \operatorname{Fin} n \times \operatorname{Fin} n$ with $p_1 \ne p_2$ of: $$X^{\min(|b^{-1}(0)|, |b^{-1}(1)|) \cdot p_1 + \max(|b^{-1}(0)|, |b^{-1}(1)|) \cdot p_2}$$ as a polynomial in $\mathbb{N}[X]$ (where $p_1, p_2$ are coerced to natural numbers, and $b^{-1}(0), b^{-1}(1)$ denote the sets of vertices mapped by $b$ to $0$ and $1$, respectively).

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

Because G is connected and has at least two vertices, it contains at least one edge, whose endpoints must receive distinct colors 0 and 1 under the proper 2-coloring b. This allows applying simple_graph_t_chromatic_ps_coeff_t_two_of_edge, which expresses the t²-coefficient as a sum of powers X^(|b⁻¹(0)| p₁ + |b⁻¹(1)| p₂) over distinct pairs (p₁, p₂). Finally, a case analysis on the relative sizes of the two color classes simplifies the minimum and maximum, using the symmetry of the sum under swapping distinct indices (fin_pair_ne_sum_pow_swap) when |b⁻¹(1)| ≤ |b⁻¹(0)|.

  1. An element of Fin 2 is nonzero if and only if it equals 1. automation

    This auxiliary lemma proves that for any a ∈ Fin 2, ¬(a = 0) ↔ a = 1 by case analysis on the two elements of Fin 2 and direct computation.

    line 1

    theorem simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two (a : Fin 2) : ¬ a = 0 ↔ a = 1 := by fin_cases a <;> decide
  2. The graph G contains at least one edge.

    Since |V| ≥ 2, the vertex set has more than one element (by linear arithmetic via omega), so there exist distinct vertices x ≠ y by Fintype.exists_pair_of_one_lt_card. Because G is connected, there is a walk p from x to y. Since x ≠ y, this walk cannot be empty; its first step gives an edge between x and an adjacent vertex, yielding adjacent vertices u, w.

    lines 12–19

    uses Fintype.exists_pair_of_one_lt_card

      classical
      obtain ⟨x, y, hxy⟩ := Fintype.exists_pair_of_one_lt_card (by omega : 1 < Fintype.card V)
      obtain ⟨p⟩ := hconn.preconnected x y
      have : ∃ u w, G.Adj u w := by
        cases p with
        | nil => exact absurd rfl hxy
        | cons h _ => exact ⟨_, _, h⟩
      obtain ⟨u, w, huw⟩ := this
  3. There exists an edge in G whose endpoints are colored 0 and 1 by the 2-coloring b.

    Because b is a proper 2-coloring and u is adjacent to w, the colors b(u) and b(w) in Fin 2 must differ. A case distinction on whether b(u) = 0 shows that either b(u) = 0 and b(w) = 1 (using simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two), so the edge (u, w) works, or b(u) ≠ 0 (hence b(u) = 1) and b(w) = 0, so the reversed edge (w, u) works by symmetry of adjacency.

    lines 20–26

    uses simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two

      have hbuw := b.valid huw
      have key : ∃ u0 w0, b u0 = 0 ∧ b w0 = 1 ∧ G.Adj u0 w0 := by
        by_cases hu : b u = 0
        · exact ⟨u, w, hu, (simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two _).1 (fun h => hbuw (hu.trans h.symm)), huw⟩
        · exact ⟨w, u, by rw [simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two] at hu; by_contra h; rw [simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two] at h; exact hbuw (hu.trans h.symm),
            (simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two _).1 hu, huw.symm⟩
      obtain ⟨u0, w0, hb0, hb1, hadj⟩ := key
  4. The coefficient of t² equals the sum over distinct pairs (p₁, p₂) of X^(|b⁻¹(0)| p₁ + |b⁻¹(1)| p₂).

    We rewrite the goal using simple_graph_t_chromatic_ps_coeff_t_two_of_edge, which applies to any connected graph with a 2-coloring and an edge connecting vertices of colors 0 and 1.

    line 27

    uses simple_graph_t_chromatic_ps_coeff_t_two_of_edge

      rw [simple_graph_t_chromatic_ps_coeff_t_two_of_edge G n hconn b u0 w0 hb0 hb1 hadj]
  5. The sum matches the required formula where the exponents are ordered by the minimum and maximum of the color class sizes.

    By totality of the ordering on ℕ (le_total), either |b⁻¹(0)| ≤ |b⁻¹(1)| or |b⁻¹(1)| ≤ |b⁻¹(0)|. In the first case, min_eq_left and max_eq_right rewrite the minimum and maximum directly into |b⁻¹(0)| and |b⁻¹(1)|. In the second case, min_eq_right and max_eq_left simplify the minimum and maximum, and fin_pair_ne_sum_pow_swap swaps the dummy summation indices p₁ and p₂ to match the LHS.

    lines 28–31

    uses le_total, min_eq_left, max_eq_right, min_eq_right, max_eq_left, fin_pair_ne_sum_pow_swap

      rcases le_total (Finset.univ.filter (fun v => b v = 0)).card
          (Finset.univ.filter (fun v => b v = 1)).card with h | h
      · rw [min_eq_left h, max_eq_right h]
      · rw [min_eq_right h, max_eq_left h, fin_pair_ne_sum_pow_swap]
simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two
For any element a in Fin 2, a is nonzero if and only if a equals 1.
Fintype.exists_pair_of_one_lt_card
A finite type with cardinality strictly greater than 1 contains at least two distinct elements.
simple_graph_t_chromatic_ps_coeff_t_two_of_edge
For a connected graph with a 2-coloring and an edge connecting a vertex colored 0 to a vertex colored 1, the t²-coefficient of its chromatic principal specialization equals the sum over distinct pairs (p₁, p₂) of X^(|b⁻¹(0)| p₁ + |b⁻¹(1)| p₂).
le_total
For any two elements a, b in a linear order, either a ≤ b or b ≤ a.
min_eq_left
If a ≤ b in a linear order, then min(a, b) = a.
max_eq_right
If a ≤ b in a linear order, then max(a, b) = b.
min_eq_right
If b ≤ a in a linear order, then min(a, b) = b.
max_eq_left
If b ≤ a in a linear order, then max(a, b) = a.
fin_pair_ne_sum_pow_swap
The sum of X^(a p₁ + b p₂) over all pairs of distinct elements (p₁, p₂) in Fin n × Fin n equals the sum of X^(b p₁ + a p₂) over the same set.

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_coeff_t_two_connected_bipartite_fin_two (a : Fin 2) : ¬ a = 0 ↔ a = 1 := by fin_cases a <;> decidetheorem simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 2 ≤ n)    (hV : 2 ≤ Fintype.card V) (hcol : G.Colorable n) (hconn : G.Connected)    (b : G.Coloring (Fin 2)) :    (simple_graph_t_chromatic_principal_specialization G n).coeff 2 =      ∑ p ∈ Finset.univ.filter (fun p : Fin n × Fin n => p.1 ≠ p.2),        Polynomial.X ^ (min (Finset.univ.filter (fun v => b v = 0)).card                            (Finset.univ.filter (fun v => b v = 1)).card * (p.1 : ℕ) +                        max (Finset.univ.filter (fun v => b v = 0)).card                            (Finset.univ.filter (fun v => b v = 1)).card * (p.2 : ℕ)) := by  classical  obtain ⟨x, y, hxy⟩ := Fintype.exists_pair_of_one_lt_card (by omega : 1 < Fintype.card V)  obtain ⟨p⟩ := hconn.preconnected x y  have : ∃ u w, G.Adj u w := by    cases p with    | nil => exact absurd rfl hxy    | cons h _ => exact ⟨_, _, h⟩  obtain ⟨u, w, huw⟩ := this  have hbuw := b.valid huw  have key : ∃ u0 w0, b u0 = 0 ∧ b w0 = 1 ∧ G.Adj u0 w0 := by    by_cases hu : b u = 0    · exact ⟨u, w, hu, (simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two _).1 (fun h => hbuw (hu.trans h.symm)), huw⟩    · exact ⟨w, u, by rw [simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two] at hu; by_contra h; rw [simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two] at h; exact hbuw (hu.trans h.symm),        (simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartite_fin_two _).1 hu, huw.symm⟩  obtain ⟨u0, w0, hb0, hb1, hadj⟩ := key  rw [simple_graph_t_chromatic_ps_coeff_t_two_of_edge G n hconn b u0 w0 hb0 hb1 hadj]  rcases le_total (Finset.univ.filter (fun v => b v = 0)).card      (Finset.univ.filter (fun v => b v = 1)).card with h | h  · rw [min_eq_left h, max_eq_right h]  · rw [min_eq_right h, max_eq_left h, fin_pair_ne_sum_pow_swap]
See it in the graphDiscuss this resultChallenge it