AFTD Auto-Formalizing Theoretical Domains

petrial_nullity_poly_leaf_rec

theoremverified

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

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

    lines 12–18

    uses SimpleGraph.degree_eq_one_iff_existsUnique_adj.mp

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

    lines 19–23

    uses Fintype.card_congr, Equiv.Set.sumCompl, Fintype.card_sum

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

    lines 24–41

    uses Subtype.ext_iff, Subtype.ext, Fintype.card_congr, Equiv.Set.sumCompl, Fintype.card_sum, Equiv.ofBijective

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

    lines 42–56

    uses Equiv.ofBijective, petrial_leaf_flip_bijective, Fintype.sum_equiv, petrial_leaf_one_pivot

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

    lines 57–75

    uses Equiv.ofBijective, petrial_leaf_restriction_bijective, Fintype.sum_equiv, petrial_leaf_zero_pivot, Fintype.sum_prod_type, Fintype.sum_bool, two_mul

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

    lines 76–79

    uses Fintype.sum_subtype_add_sum_subtype

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

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

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