AFTD Auto-Formalizing Theoretical Domains

petrial_nullity_poly_empty_induced

theoremverified

The partial Petrial nullity generating polynomial of the empty induced graph is one.

Statement

theorem petrial_nullity_poly_empty_induced {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : petrial_nullity_poly (G.induce (∅ : Set V)) = 1
Source
Empty base case for the OP-1239 leaf-deletion certificate.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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_matrixGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset F : Finset V,…
Used by 1

The proof, explained

By definition, the partial Petrial nullity polynomial is a sum over all vertex subsets of X^(|V| - rank(M_F)). For the induced subgraph on the empty set, the number of vertices is zero, so the exponent 0 - rank(M_F) vanishes in natural number subtraction, making every summand X^0 = 1. Since the empty set has only one subset (the empty set itself), the sum reduces to a single term equal to 1.

  1. By definition, the polynomial is expressed as a sum over all subsets of the empty vertex set.

    Unfolding `petrial_nullity_poly` expands the goal into the definition ∑ F, X ^ (|∅| - rank(M_F)) = 1, where the summation indexes over all subsets F of the vertex set of the empty induced subgraph.

    line 2

      unfold petrial_nullity_poly
  2. Every summand in the sum is equal to 1, reducing the sum to ∑ F, 1 = 1.

    The vertex set of the induced empty subgraph has cardinality 0 by `Fintype.card_eq_zero`. For any vertex subset F, the exponent |∅| - rank(M_F) becomes 0 - rank(M_F) = 0 by truncated natural subtraction (`Nat.zero_sub`). Since any element to the power 0 is 1 (`pow_zero`), every summand equals 1, and rewriting the sum replaces each term with 1.

    lines 3–7

    uses Fintype.card_eq_zero, Nat.zero_sub, pow_zero

      have hcard : Fintype.card (↥(∅ : Set V)) = 0 := Fintype.card_eq_zero
      have hterm : ∀ F : Finset (↥(∅ : Set V)), (Polynomial.X : Polynomial ℕ) ^ (Fintype.card (↥(∅ : Set V)) - (petrial_matrix (G.induce (∅ : Set V)) F).rank) = 1 := by
        intro F
        rw [hcard, Nat.zero_sub, pow_zero]
      simp_rw [hterm]
  3. The universe of subsets of the empty set consists solely of the empty set, univ = {∅}.

    By set extensionality (`ext`), two families of subsets are equal if they have the same members. By `Finset.mem_univ`, `Finset.mem_singleton`, and `true_iff`, this reduces to showing that any subset F of the empty set equals ∅. Applying extensionality again (`ext x`), we must show x ∈ F ↔ x ∈ ∅ for all x in the empty vertex set, which holds vacuously by `IsEmpty.elim` (with typeclass instance found by `inferInstance`) because no such x exists.

    lines 8–12

    uses Finset.mem_univ, Finset.mem_singleton, true_iff, IsEmpty.elim, inferInstance

      have : (Finset.univ : Finset (Finset (↥(∅ : Set V)))) = {∅} := by
        ext F
        simp only [Finset.mem_univ, Finset.mem_singleton, true_iff]
        ext x
        exact IsEmpty.elim inferInstance x
  4. The sum over {∅} evaluates to 1.

    Substituting the universe of subsets with {∅} turns the sum into ∑ F ∈ {∅}, 1 = 1, which simplifies directly to 1.

    lines 13–14

      rw [this]
      simp
Fintype.card_eq_zero
An empty finite type has cardinality zero.
Nat.zero_sub
Subtracting any natural number from zero in ℕ yields zero.
pow_zero
Any element raised to the zeroth power equals one.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Finset.mem_singleton
An element belongs to a singleton set if and only if it equals the sole element of that singleton.
true_iff
The equivalence True ↔ p simplifies to p.
IsEmpty.elim
From an element of an empty type, any conclusion follows vacuously (the principle of explosion).
inferInstance
Synthesizes an instance of a typeclass available in scope.

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 petrial_nullity_poly_empty_induced {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : petrial_nullity_poly (G.induce (∅ : Set V)) = 1 := by  unfold petrial_nullity_poly  have hcard : Fintype.card (↥(∅ : Set V)) = 0 := Fintype.card_eq_zero  have hterm : ∀ F : Finset (↥(∅ : Set V)), (Polynomial.X : Polynomial ℕ) ^ (Fintype.card (↥(∅ : Set V)) - (petrial_matrix (G.induce (∅ : Set V)) F).rank) = 1 := by    intro F    rw [hcard, Nat.zero_sub, pow_zero]  simp_rw [hterm]  have : (Finset.univ : Finset (Finset (↥(∅ : Set V)))) = {∅} := by    ext F    simp only [Finset.mem_univ, Finset.mem_singleton, true_iff]    ext x    exact IsEmpty.elim inferInstance x  rw [this]  simp
See it in the graphDiscuss this resultChallenge it