petrial_nullity_poly_leaf_rec
For a finite graph G with a degree-one vertex v whose neighbour is u, the nullity generating polynomial of G equals the nullity generating polynomial of G with v deleted, plus twice the nullity generating polynomial of G with u and v deleted.
Statement
theorem petrial_nullity_poly_leaf_rec {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] {v u : V} (hv : T.degree v = 1) (hu : T.Adj v u) : petrial_nullity_poly T = petrial_nullity_poly (T.induce ({v}ᶜ : Set V)) + 2 * petrial_nullity_poly (T.induce (({u} ∪ {v})ᶜ : Set V))
- Source
- step towards op_1239_max_degree_three_tree_petrial_log_concave
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- petrial_nullity_polyThe nullity generating polynomial of a finite graph G on V: the sum over all vertex subsets F of w raised to the nullity of the partial…
- petrial_nullity_poly_coeff_eq_petrial_coeffFor every finite graph G on V and every k ≤ |V|, the coefficient of w^(|V| - k) in the nullity generating polynomial equals petrial_coeff…
- petrial_matrix_rank_le_cardFor any finite simple graph G and any subset F of vertices, the rank of the petrial matrix of G and F over ZMod 2 is at most the number of…
- petrial_leaf_flip_bijectiveFor distinct vertices v and u, restricting a vertex subset containing v to the complement of v and toggling u is a bijection onto all…
- petrial_leaf_restriction_bijectiveFor distinct vertices v and u, a vertex subset omitting v is uniquely determined by its membership bit at u and its restriction to the…
- petrial_leaf_one_pivotIf v is a leaf with unique neighbor u and the diagonal perturbation includes v, the perturbed matrix rank is one plus the rank on the…
- petrial_leaf_zero_pivotFor a graph with a leaf v and unique neighbor u, if v is absent from the perturbation then its matrix rank is two plus the rank on the…
- petrial_matrixGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset F : Finset V,…
- petrial_leaf_restrictionRestrict a finite vertex subset to the complement of vertices u and v.
- petrial_leaf_flipFor vertices v and u and a vertex subset F, restrict F to the complement of v and toggle membership of u.
- Used by 1
- petrial_nullity_poly_leaf_finsetIf v is a leaf with neighbor u in the subgraph induced by the finite set s, its nullity polynomial is that after deleting v plus twice…
The proof, explained
The proof partitions the sum defining the nullity polynomial p(T) into two parts according to whether the leaf vertex v belongs to F or not. When v ∈ F, pivoting on the leaf vertex v reduces the matrix rank by 1 and flips whether u ∈ F, which bijectively matches the subsets of T - v and produces p(T - v). When v ∉ F, pivoting on the 2 × 2 block {u, v} reduces the rank by 2 regardless of whether u ∈ F, giving a 2-to-1 correspondence with subsets of T - {u, v} that produces 2 * p(T - {u, v}). Summing these two contributions yields the leaf-elimination recurrence p(T) = p(T - v) + 2 * p(T - {u, v}).
The vertices v and u are distinct, and u is the unique vertex adjacent to v in T.
Since v is adjacent to u in the simple graph T, irreflexivity gives v ≠ u. Because v has degree 1, there exists a unique neighbor w of v. Transitivity through this unique witness w shows that any vertex z adjacent to v must equal u.
uses
SimpleGraph.degree_eq_one_iff_existsUnique_adj.mpclassical have hvu : v ≠ u := T.ne_of_adj hu have huv : u ≠ v := hvu.symm obtain ⟨w, hw, hwuniq⟩ := SimpleGraph.degree_eq_one_iff_existsUnique_adj.mp hv have huniq : ∀ z, T.Adj v z → z = u := by intro z hz exact (hwuniq z hz).trans (hwuniq u hu).symm
The vertex set has cardinality |V| = 1 + |V \ {v}|.
The singleton {v} and its complement partition V via Equiv.Set.sumCompl. Applying Fintype.card_congr and Fintype.card_sum, together with the fact that the singleton has cardinality 1, linear arithmetic yields |V| = 1 + |V \ {v}|.
uses
Fintype.card_congr,Equiv.Set.sumCompl,Fintype.card_sumhave hc1 : Fintype.card V = 1 + Fintype.card (({v}ᶜ : Set V)) := by have h := Fintype.card_congr (Equiv.Set.sumCompl ({v} : Set V)) simp only [Fintype.card_sum] at h have hc : Fintype.card ({v} : Set V) = 1 := by simp omega
The vertex set has cardinality |V| = 2 + |V \ {u, v}|.
Let P = {u, v}. Since u ≠ v, mapping 0 to v and 1 to u defines a bijection from Fin 2 to P, so P has cardinality 2. Partitioning V into P and Pᶜ via Equiv.Set.sumCompl and taking cardinalities shows |V| = 2 + |V \ {u, v}|.
uses
Subtype.ext_iff,Subtype.ext,Fintype.card_congr,Equiv.Set.sumCompl,Fintype.card_sum,Equiv.ofBijectivehave hc2 : Fintype.card V = 2 + Fintype.card (({u, v}ᶜ : Set V)) := by let P : Set V := {u, v} let f : Fin 2 → P := fun i => if i = 0 then ⟨v, by simp [P]⟩ else ⟨u, by simp [P]⟩ have hf : Function.Bijective f := by constructor · intro i j h fin_cases i <;> fin_cases j <;> simp [f, Subtype.ext_iff, hvu, huv] at h ⊢ · intro x have hx : (x : V) = u ∨ (x : V) = v := x.2 rcases hx with hx | hx · refine ⟨1, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm · refine ⟨0, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm have h := Fintype.card_congr (Equiv.Set.sumCompl P) simp only [Fintype.card_sum] at h have hP : Fintype.card P = 2 := by simpa using (Fintype.card_congr (Equiv.ofBijective f hf)).symm change Fintype.card V = 2 + Fintype.card (Pᶜ : Set V) omega
The sum over all subsets F ⊆ V containing v equals the nullity polynomial of T induced on V \ {v}.
The leaf-flip map provides a bijection e1 between subsets containing v and subsets of V \ {v}. Pivoting on the leaf v reduces the rank of the petrial matrix by 1 (petrial_leaf_one_pivot). Because |V| also exceeds |V \ {v}| by 1, the exponent |V| - rank(petrial_matrix) is preserved under e1. Reindexing the sum with Fintype.sum_equiv yields petrial_nullity_poly (T - v).
uses
Equiv.ofBijective,petrial_leaf_flip_bijective,Fintype.sum_equiv,petrial_leaf_one_pivotlet e1 : {F : Finset V // v ∈ F} ≃ Finset (({v}ᶜ : Set V)) := Equiv.ofBijective _ (petrial_leaf_flip_bijective v u huv) have hsum1 : (∑ F : {F : Finset V // v ∈ F}, (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F.1).rank)) = petrial_nullity_poly (T.induce ({v}ᶜ : Set V)) := by unfold petrial_nullity_poly apply Fintype.sum_equiv e1 intro F change (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F.1).rank) = (X : Polynomial ℕ) ^ (Fintype.card (({v}ᶜ : Set V)) - (petrial_matrix (T.induce ({v}ᶜ : Set V)) (petrial_leaf_flip v u F.1)).rank) rw [petrial_leaf_one_pivot T v u F.1 F.2 hu huniq, hc1] congr 1 omega
The sum over all subsets F ⊆ V not containing v equals 2 * petrial_nullity_poly (T - {u, v}).
Restricting F to V \ {u, v} while recording whether u ∈ F gives a bijection e0 from subsets avoiding v to Bool × Finset (V \ {u, v}). Pivoting on the 2 × 2 block {u, v} reduces the rank of the petrial matrix by 2 (petrial_leaf_zero_pivot). Since |V| = 2 + |V \ {u, v}|, the exponents match. Summing over e0, splitting the product into iterated sums, and summing over Bool doubles the nullity polynomial of T - {u, v}.
uses
Equiv.ofBijective,petrial_leaf_restriction_bijective,Fintype.sum_equiv,petrial_leaf_zero_pivot,Fintype.sum_prod_type,Fintype.sum_bool,two_mullet e0 : {F : Finset V // v ∉ F} ≃ Bool × Finset (({u,v}ᶜ : Set V)) := Equiv.ofBijective _ (petrial_leaf_restriction_bijective v u hvu) have hsum0 : (∑ F : {F : Finset V // v ∉ F}, (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F.1).rank)) = 2 * petrial_nullity_poly (T.induce (({u,v}ᶜ : Set V))) := by have hsum := Fintype.sum_equiv e0 (fun F => (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F.1).rank)) (fun p => (X : Polynomial ℕ) ^ (Fintype.card (({u,v}ᶜ : Set V)) - (petrial_matrix (T.induce (({u,v}ᶜ : Set V))) p.2).rank)) (by intro F change (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F.1).rank) = (X : Polynomial ℕ) ^ (Fintype.card (({u,v}ᶜ : Set V)) - (petrial_matrix (T.induce (({u,v}ᶜ : Set V))) (petrial_leaf_restriction v u F.1)).rank) rw [petrial_leaf_zero_pivot T v u F.1 F.2 hu huniq, hc2] congr 1 omega) rw [hsum, Fintype.sum_prod_type, Fintype.sum_bool] simp only [petrial_nullity_poly, two_mul]
The nullity polynomial of T satisfies p(T) = p(T - v) + 2 * p(T - {u, v}).
By Fintype.sum_subtype_add_sum_subtype, the total sum over all subsets F ⊆ V is the sum of the terms with v ∈ F and the terms with v ∉ F. Substituting the evaluations from the previous two steps yields the recurrence.
uses
Fintype.sum_subtype_add_sum_subtypechange (∑ F : Finset V, (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F).rank)) = petrial_nullity_poly (T.induce ({v}ᶜ : Set V)) + 2 * petrial_nullity_poly (T.induce (({u,v}ᶜ : Set V))) rw [← Fintype.sum_subtype_add_sum_subtype (fun F : Finset V => v ∈ F), hsum1, hsum0]
SimpleGraph.degree_eq_one_iff_existsUnique_adj.mp- If a vertex in a graph has degree 1, then there exists a unique vertex adjacent to it.
Fintype.card_congr- An equivalence (bijection) between two finite types implies that they have the same cardinality.
Equiv.Set.sumCompl- A set and its complement partition the ambient type, inducing a bijection between their disjoint sum and the ambient type.
Fintype.card_sum- The cardinality of the disjoint sum of two finite types is the sum of their individual cardinalities.
Subtype.ext_iff- Two elements of a subtype are equal if and only if their underlying values are equal.
Subtype.ext- Two elements of a subtype are equal whenever their underlying values are equal.
Equiv.ofBijective- A bijective function can be packaged into an equivalence (invertible map).
petrial_leaf_flip_bijective- The leaf-flip operation is a bijection from the subsets containing a leaf vertex v to the subsets of V \ {v}.
Fintype.sum_equiv- A sum over a finite index type can be reindexed along an equivalence, provided the summand values correspond under the bijection.
petrial_leaf_one_pivot- If v is a leaf adjacent to u and v ∈ F, the rank of the petrial matrix of G on F is 1 plus the rank of the petrial matrix of G - v on the flipped subset.
petrial_leaf_restriction_bijective- The restriction operation, paired with a boolean indicating whether u ∈ F, is a bijection from subsets not containing v to Bool × Finset (V \ {u, v}).
petrial_leaf_zero_pivot- If v is a leaf adjacent to u and v ∉ F, the rank of the petrial matrix of G on F is 2 plus the rank of the petrial matrix of G - {u, v} on the restricted subset.
Fintype.sum_prod_type- A sum over a Cartesian product of two finite types decomposes into nested sums over the individual factors.
Fintype.sum_bool- A sum over Bool evaluates to the value at true plus the value at false.
two_mul- Multiplying by 2 is equivalent to repeated addition: 2 * n = n + n.
Fintype.sum_subtype_add_sum_subtype- A sum over a finite type equals the sum over elements satisfying a predicate plus the sum over elements satisfying its negation.
- The fact that the set {u, v} has cardinality 2 is verified formally by constructing an explicit bijection from Fin 2 and checking all four index pairs, a formal detail that would typically be taken as obvious on paper.
- The set ({u} ∪ {v})ᶜ in the theorem statement is definitionally equal to {u, v}ᶜ, which the proof substitutes transparently using change.
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.
open Polynomialset_option maxRecDepth 10000set_option maxHeartbeats 0/-- Leaf-elimination recursion: if v is a vertex of degree 1 with neighbour u, the nullity polynomial satisfies p(G) = p(G - v) + 2 * p(G - {u,v}). -/theorem petrial_nullity_poly_leaf_rec {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] {v u : V} (hv : T.degree v = 1) (hu : T.Adj v u) : petrial_nullity_poly T = petrial_nullity_poly (T.induce ({v}ᶜ : Set V)) + 2 * petrial_nullity_poly (T.induce (({u} ∪ {v})ᶜ : Set V)) := by classical have hvu : v ≠ u := T.ne_of_adj hu have huv : u ≠ v := hvu.symm obtain ⟨w, hw, hwuniq⟩ := SimpleGraph.degree_eq_one_iff_existsUnique_adj.mp hv have huniq : ∀ z, T.Adj v z → z = u := by intro z hz exact (hwuniq z hz).trans (hwuniq u hu).symm have hc1 : Fintype.card V = 1 + Fintype.card (({v}ᶜ : Set V)) := by have h := Fintype.card_congr (Equiv.Set.sumCompl ({v} : Set V)) simp only [Fintype.card_sum] at h have hc : Fintype.card ({v} : Set V) = 1 := by simp omega have hc2 : Fintype.card V = 2 + Fintype.card (({u, v}ᶜ : Set V)) := by let P : Set V := {u, v} let f : Fin 2 → P := fun i => if i = 0 then ⟨v, by simp [P]⟩ else ⟨u, by simp [P]⟩ have hf : Function.Bijective f := by constructor · intro i j h fin_cases i <;> fin_cases j <;> simp [f, Subtype.ext_iff, hvu, huv] at h ⊢ · intro x have hx : (x : V) = u ∨ (x : V) = v := x.2 rcases hx with hx | hx · refine ⟨1, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm · refine ⟨0, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm have h := Fintype.card_congr (Equiv.Set.sumCompl P) simp only [Fintype.card_sum] at h have hP : Fintype.card P = 2 := by simpa using (Fintype.card_congr (Equiv.ofBijective f hf)).symm change Fintype.card V = 2 + Fintype.card (Pᶜ : Set V) omega let e1 : {F : Finset V // v ∈ F} ≃ Finset (({v}ᶜ : Set V)) := Equiv.ofBijective _ (petrial_leaf_flip_bijective v u huv) have hsum1 : (∑ F : {F : Finset V // v ∈ F}, (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F.1).rank)) = petrial_nullity_poly (T.induce ({v}ᶜ : Set V)) := by unfold petrial_nullity_poly apply Fintype.sum_equiv e1 intro F change (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F.1).rank) = (X : Polynomial ℕ) ^ (Fintype.card (({v}ᶜ : Set V)) - (petrial_matrix (T.induce ({v}ᶜ : Set V)) (petrial_leaf_flip v u F.1)).rank) rw [petrial_leaf_one_pivot T v u F.1 F.2 hu huniq, hc1] congr 1 omega let e0 : {F : Finset V // v ∉ F} ≃ Bool × Finset (({u,v}ᶜ : Set V)) := Equiv.ofBijective _ (petrial_leaf_restriction_bijective v u hvu) have hsum0 : (∑ F : {F : Finset V // v ∉ F}, (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F.1).rank)) = 2 * petrial_nullity_poly (T.induce (({u,v}ᶜ : Set V))) := by have hsum := Fintype.sum_equiv e0 (fun F => (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F.1).rank)) (fun p => (X : Polynomial ℕ) ^ (Fintype.card (({u,v}ᶜ : Set V)) - (petrial_matrix (T.induce (({u,v}ᶜ : Set V))) p.2).rank)) (by intro F change (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F.1).rank) = (X : Polynomial ℕ) ^ (Fintype.card (({u,v}ᶜ : Set V)) - (petrial_matrix (T.induce (({u,v}ᶜ : Set V))) (petrial_leaf_restriction v u F.1)).rank) rw [petrial_leaf_zero_pivot T v u F.1 F.2 hu huniq, hc2] congr 1 omega) rw [hsum, Fintype.sum_prod_type, Fintype.sum_bool] simp only [petrial_nullity_poly, two_mul] change (∑ F : Finset V, (X : Polynomial ℕ) ^ (Fintype.card V - (petrial_matrix T F).rank)) = petrial_nullity_poly (T.induce ({v}ᶜ : Set V)) + 2 * petrial_nullity_poly (T.induce (({u,v}ᶜ : Set V))) rw [← Fintype.sum_subtype_add_sum_subtype (fun F : Finset V => v ∈ F), hsum1, hsum0]