simple_graph_t_chromatic_ps_coeff_t_two_of_edge
Let G be a connected finite simple graph with a proper 2-coloring b : V → Fin 2 and an edge u0 w0 with b u0 = 0, b w0 = 1. Let s0, s1 be the numbers of vertices with b = 0 and b = 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 Fin n of q^(s0 j1 + s1 j2).
Statement
theorem simple_graph_t_chromatic_ps_coeff_t_two_of_edge {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hconn : G.Connected) (b : G.Coloring (Fin 2)) (u0 w0 : V) (hb0 : b u0 = 0) (hb1 : b w0 = 1) (hadj : G.Adj u0 w0) : (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 ^ ((Finset.univ.filter (fun v => b v = 0)).card * (p.1 : ℕ) + (Finset.univ.filter (fun v => b v = 1)).card * (p.2 : ℕ))
- Source
- arXiv:2610.31785 (Principal specializations of the t-chromatic symmetric function), Proposition 3.16(3) with the parts in the order given by b
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_coeff_t_eq_sumFor a finite simple graph G and natural numbers n, k, the coefficient of t^k in ps_n(Z_G(x; t)) is the polynomial in q equal to the sum of…
- simple_graph_coloring_two_colours_const_on_bipartitionLet G be a connected finite simple graph with a proper 2-coloring b : V → Fin 2, and let u0, w0 be adjacent with b u0 = 0 and b w0 = 1.…
- Used by 1
- simple_graph_t_chromatic_ps_coeff_t_two_connected_bipartiteLet 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 →…
The proof, explained
The coefficient of t^2 in the principal specialization of the chromatic polynomial is the sum of X^(∑_v c(v)) over all proper colorings c : V → Fin n using exactly 2 colors. Because G is connected and bipartite with proper 2-coloring b, any proper 2-coloring c is completely determined by its values on the two parts of the bipartition, which are witnessed by the endpoints of the edge u0 w0. We establish a bijection between ordered pairs of distinct colors (p.1, p.2) and proper 2-colorings of G by assigning color p.1 where b = 0 and p.2 where b = 1, inverting the map c ↦ (c u0, c w0). The total color weight under this assignment equals |b⁻¹(0)| · p.1 + |b⁻¹(1)| · p.2, so the bijection equates the two sums.
In Fin 2, an element is non-zero if and only if it equals 1.
As a preliminary lemma, we verify by exhaustive case analysis on Fin 2 that 0 and 1 are the only elements, so any element distinct from 0 must be 1.
theorem simple_graph_t_chromatic_ps_coeff_t_two_of_edge_fin_two (a : Fin 2) : ¬ a = 0 ↔ a = 1 := by fin_cases a <;> decide
The coefficient of t^2 in the principal specialization equals the sum of X^(∑_v c(v)) over all proper colorings c : V → Fin n using exactly 2 colors.
We rewrite the coefficient of t^2 using the general formula simple_graph_t_chromatic_ps_coeff_t_eq_sum specialized to k = 2.
uses
simple_graph_t_chromatic_ps_coeff_t_eq_sumclassical rw [simple_graph_t_chromatic_ps_coeff_t_eq_sum]For any pair of distinct colors (p.1, p.2), assigning color p.1 to vertices where b = 0 and p.2 to vertices where b = 1 defines a valid proper coloring φ p of G.
Given adjacent vertices x and y, properness of b ensures b x ≠ b y. A case analysis on whether b x = 0 and b y = 0 shows they cannot both be 0 and cannot both be 1 (by lemma simple_graph_t_chromatic_ps_coeff_t_two_of_edge_fin_two), so one vertex is assigned p.1 and the other p.2. Since p.1 ≠ p.2, the assigned colors are distinct.
uses
if_pos,if_neg,simple_graph_t_chromatic_ps_coeff_t_two_of_edge_fin_twolet φ : Fin n × Fin n → V → Fin n := fun p v => if b v = 0 then p.1 else p.2 have hφv : ∀ p : Fin n × Fin n, p.1 ≠ p.2 → ∀ x y, G.Adj x y → φ p x ≠ φ p y := by intro p hp x y h have hb := b.valid h simp only [φ] by_cases hx : b x = 0 <;> by_cases hy : b y = 0 · exact absurd (hx.trans hy.symm) hb · rw [if_pos hx, if_neg hy]; exact hp · rw [if_neg hx, if_pos hy]; exact fun e => hp e.symm · rw [simple_graph_t_chromatic_ps_coeff_t_two_of_edge_fin_two] at hx hy; exact absurd (hx.trans hy.symm) hb
The sum of the color values of φ p over all vertices equals |b⁻¹(0)| · p.1 + |b⁻¹(1)| · p.2.
We split the sum over V into vertices where b v = 0 and vertices where b v ≠ 0 using Finset.sum_ite. On each subset the summand is constant, yielding |b⁻¹(0)| · p.1 and |{v | b v ≠ 0}| · p.2 via Finset.sum_const. Lemma simple_graph_t_chromatic_ps_coeff_t_two_of_edge_fin_two then identifies {v | b v ≠ 0} with {v | b v = 1}.
uses
Finset.sum_ite,Finset.sum_const,smul_eq_mul,congrArg,Finset.filter_congr,simple_graph_t_chromatic_ps_coeff_t_two_of_edge_fin_twohave hW : ∀ p : Fin n × Fin n, ∑ v : V, (φ p v : ℕ) = (Finset.univ.filter (fun v => b v = 0)).card * (p.1 : ℕ) + (Finset.univ.filter (fun v => b v = 1)).card * (p.2 : ℕ) := by intro p simp only [φ] rw [show (fun v => ((if b v = 0 then p.1 else p.2 : Fin n) : ℕ)) = (fun v => if b v = 0 then (p.1 : ℕ) else (p.2 : ℕ)) from funext fun v => by split_ifs <;> rfl] rw [Finset.sum_ite, Finset.sum_const, Finset.sum_const, smul_eq_mul, smul_eq_mul] congr 2 exact congrArg Finset.card (Finset.filter_congr (fun v _ => simple_graph_t_chromatic_ps_coeff_t_two_of_edge_fin_two (b v)))
It suffices to construct a bijection between pairs of distinct colors (p.1, p.2) and proper 2-colorings of G that preserves the exponent of X.
We reverse the equality and apply Finset.sum_bij'. The candidate bijection maps a pair p to the coloring φ p, and in the reverse direction maps a 2-coloring c to the pair (c u0, c w0) of colors at the endpoints of the edge u0 w0.
uses
Finset.sum_bij',SimpleGraph.Coloring.mksymm refine Finset.sum_bij' (fun p hp => SimpleGraph.Coloring.mk (φ p) (fun h e => hφv p (Finset.mem_filter.1 hp).2 _ _ h e)) (fun c _ => (c u0, c w0)) ?_ ?_ ?_ ?_ ?_
For any pair of distinct colors p, the coloring φ p uses exactly 2 colors.
We prove that the image of φ p on V is exactly {p.1, p.2}. The inclusion ⊆ holds because every vertex is assigned either p.1 or p.2. Conversely, u0 is sent to p.1 (since b u0 = 0) and w0 is sent to p.2 (since b w0 = 1), so {p.1, p.2} ⊆ im(φ p). Since p.1 ≠ p.2, the set {p.1, p.2} has cardinality 2 by Finset.card_pair, and so |im(φ p)| = 2.
uses
Finset.eq_of_subset_of_card_le,Finset.card_le_card,Finset.card_pair· intro p hp have hp' := (Finset.mem_filter.1 hp).2 simp only [Finset.mem_filter, Finset.mem_univ, true_and] have : Finset.univ.image (SimpleGraph.Coloring.mk (φ p) (fun h e => hφv p hp' _ _ h e) : V → Fin n) = {p.1, p.2} := by apply Finset.eq_of_subset_of_card_le · intro y hy simp only [Finset.mem_image, Finset.mem_univ, true_and] at hy obtain ⟨v, rfl⟩ := hy show φ p v ∈ _ simp only [φ]; split_ifs <;> simp · apply Finset.card_le_card intro y hy simp only [Finset.mem_insert, Finset.mem_singleton] at hy simp only [Finset.mem_image, Finset.mem_univ, true_and] rcases hy with rfl | rfl · exact ⟨u0, by show φ p u0 = _; simp [φ, hb0]⟩ · exact ⟨w0, by show φ p w0 = _; simp [φ, hb1]⟩ rw [this, Finset.card_pair hp']
For any proper 2-coloring c, the pair (c u0, c w0) has distinct coordinates.
Since u0 and w0 are adjacent, any proper coloring c must assign them different colors, so c u0 ≠ c w0.
· intro c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact c.valid hadj
The reverse map is a left inverse: evaluating φ p at u0 and w0 recovers the pair p.
By definition of φ, φ p u0 = p.1 because b u0 = 0, and φ p w0 = p.2 because b w0 = 1.
uses
Prod.ext· intro p hp exact Prod.ext (by show (if b u0 = 0 then p.1 else p.2) = p.1; simp [hb0]) (by show (if b w0 = 0 then p.1 else p.2) = p.2; simp [hb1])
The reverse map is a right inverse: reconstructing a coloring from (c u0, c w0) via φ recovers c.
Because G is connected, simple_graph_coloring_two_colours_const_on_bipartition implies that every proper 2-coloring c is constant on the two parts of the bipartition defined by b. Thus c v equals c u0 when b v = 0 and c w0 when b v = 1, which coincides with φ (c u0, c w0) v.
uses
simple_graph_coloring_two_colours_const_on_bipartition· intro c hc have hc' := (Finset.mem_filter.1 hc).2 ext v show (φ (c u0, c w0) v : ℕ) = c v rw [simple_graph_coloring_two_colours_const_on_bipartition G n hconn b u0 w0 hb0 hb1 hadj c hc' v]
The summands under the bijection match.
The exponent of X for the pair p in the sum matches ∑_v φ p v by the identity established in lemma hW.
· intro p hp rw [← hW p] rfl
simple_graph_t_chromatic_ps_coeff_t_eq_sum- The coefficient of t^k in the principal specialization of the chromatic polynomial is the sum of X^(∑_v c(v)) over all proper colorings c whose image has cardinality k.
if_pos- If condition c is true, then (if c then t else e) evaluates to t.
if_neg- If condition c is false, then (if c then t else e) evaluates to e.
simple_graph_t_chromatic_ps_coeff_t_two_of_edge_fin_two- For any element a of Fin 2, a ≠ 0 if and only if a = 1.
Finset.sum_ite- Splits a sum over a finite set of an if-then-else expression into a sum over elements satisfying the condition and a sum over elements satisfying its negation.
Finset.sum_const- The sum of a constant value over a finite set equals the cardinality of the set times that value.
smul_eq_mul- Scalar multiplication by a natural number equals standard multiplication.
congrArg- If two inputs are equal, a function applied to them yields equal outputs.
Finset.filter_congr- Two filtered sub-finsets are equal if their defining predicates are logically equivalent on all elements of the set.
Finset.sum_bij'- Two finite sums are equal if there is a bijection between their index sets that preserves corresponding terms.
SimpleGraph.Coloring.mk- Constructs a proper coloring of a simple graph from a vertex coloring function and a proof that adjacent vertices receive distinct colors.
Finset.eq_of_subset_of_card_le- If a finite set s is a subset of t and the cardinality of t is at most that of s, then s and t are equal.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.card_pair- The cardinality of the two-element set {a, b} is 2 whenever a ≠ b.
Prod.ext- Two ordered pairs are equal if and only if their first components are equal and their second components are equal.
simple_graph_coloring_two_colours_const_on_bipartition- On a connected graph with a proper 2-coloring b and an edge u0 w0 with b u0 = 0 and b w0 = 1, any proper 2-coloring c is constant on the color classes of b, taking value c u0 where b = 0 and c w0 where b = 1.
- In the Lean formalization, Polynomial.X plays the role of the variable q from the English theorem statement, while the coefficient of t^2 is extracted directly via coeff 2 on the principal specialization.
- The uniqueness of the bipartition on connected graphs is encapsulated in the helper lemma simple_graph_coloring_two_colours_const_on_bipartition.
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_coeff_t_two_of_edge_fin_two (a : Fin 2) : ¬ a = 0 ↔ a = 1 := by fin_cases a <;> decidetheorem simple_graph_t_chromatic_ps_coeff_t_two_of_edge {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hconn : G.Connected) (b : G.Coloring (Fin 2)) (u0 w0 : V) (hb0 : b u0 = 0) (hb1 : b w0 = 1) (hadj : G.Adj u0 w0) : (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 ^ ((Finset.univ.filter (fun v => b v = 0)).card * (p.1 : ℕ) + (Finset.univ.filter (fun v => b v = 1)).card * (p.2 : ℕ)) := by classical rw [simple_graph_t_chromatic_ps_coeff_t_eq_sum] let φ : Fin n × Fin n → V → Fin n := fun p v => if b v = 0 then p.1 else p.2 have hφv : ∀ p : Fin n × Fin n, p.1 ≠ p.2 → ∀ x y, G.Adj x y → φ p x ≠ φ p y := by intro p hp x y h have hb := b.valid h simp only [φ] by_cases hx : b x = 0 <;> by_cases hy : b y = 0 · exact absurd (hx.trans hy.symm) hb · rw [if_pos hx, if_neg hy]; exact hp · rw [if_neg hx, if_pos hy]; exact fun e => hp e.symm · rw [simple_graph_t_chromatic_ps_coeff_t_two_of_edge_fin_two] at hx hy; exact absurd (hx.trans hy.symm) hb have hW : ∀ p : Fin n × Fin n, ∑ v : V, (φ p v : ℕ) = (Finset.univ.filter (fun v => b v = 0)).card * (p.1 : ℕ) + (Finset.univ.filter (fun v => b v = 1)).card * (p.2 : ℕ) := by intro p simp only [φ] rw [show (fun v => ((if b v = 0 then p.1 else p.2 : Fin n) : ℕ)) = (fun v => if b v = 0 then (p.1 : ℕ) else (p.2 : ℕ)) from funext fun v => by split_ifs <;> rfl] rw [Finset.sum_ite, Finset.sum_const, Finset.sum_const, smul_eq_mul, smul_eq_mul] congr 2 exact congrArg Finset.card (Finset.filter_congr (fun v _ => simple_graph_t_chromatic_ps_coeff_t_two_of_edge_fin_two (b v))) symm refine Finset.sum_bij' (fun p hp => SimpleGraph.Coloring.mk (φ p) (fun h e => hφv p (Finset.mem_filter.1 hp).2 _ _ h e)) (fun c _ => (c u0, c w0)) ?_ ?_ ?_ ?_ ?_ · intro p hp have hp' := (Finset.mem_filter.1 hp).2 simp only [Finset.mem_filter, Finset.mem_univ, true_and] have : Finset.univ.image (SimpleGraph.Coloring.mk (φ p) (fun h e => hφv p hp' _ _ h e) : V → Fin n) = {p.1, p.2} := by apply Finset.eq_of_subset_of_card_le · intro y hy simp only [Finset.mem_image, Finset.mem_univ, true_and] at hy obtain ⟨v, rfl⟩ := hy show φ p v ∈ _ simp only [φ]; split_ifs <;> simp · apply Finset.card_le_card intro y hy simp only [Finset.mem_insert, Finset.mem_singleton] at hy simp only [Finset.mem_image, Finset.mem_univ, true_and] rcases hy with rfl | rfl · exact ⟨u0, by show φ p u0 = _; simp [φ, hb0]⟩ · exact ⟨w0, by show φ p w0 = _; simp [φ, hb1]⟩ rw [this, Finset.card_pair hp'] · intro c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact c.valid hadj · intro p hp exact Prod.ext (by show (if b u0 = 0 then p.1 else p.2) = p.1; simp [hb0]) (by show (if b w0 = 0 then p.1 else p.2) = p.2; simp [hb1]) · intro c hc have hc' := (Finset.mem_filter.1 hc).2 ext v show (φ (c u0, c w0) v : ℕ) = c v rw [simple_graph_coloring_two_colours_const_on_bipartition G n hconn b u0 w0 hb0 hb1 hadj c hc' v] · intro p hp rw [← hW p] rfl