AFTD Auto-Formalizing Theoretical Domains

petrial_nullity_poly_induce_induce

theoremverified

The nullity polynomial obtained by inducing on s and then on vertices in t equals the polynomial of the graph induced on the intersection of s and t.

Statement

theorem petrial_nullity_poly_induce_induce {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (s t : Set V) [DecidablePred (· ∈ s)] [DecidablePred (· ∈ t)] : petrial_nullity_poly ((G.induce s).induce {x : s | (x : V) ∈ t}) = petrial_nullity_poly (G.induce (s ∩ t))
Source
Induced-subgraph bookkeeping for the OP-1239 candidate.
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_nullity_poly_isoIsomorphic finite simple graphs have the same partial Petrial nullity generating polynomial.
Used by 2

Lean source view module on GitHub

theorem petrial_nullity_poly_induce_induce {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (s t : Set V) [DecidablePred (· ∈ s)] [DecidablePred (· ∈ t)] : petrial_nullity_poly ((G.induce s).induce {x : s | (x : V) ∈ t}) = petrial_nullity_poly (G.induce (s ∩ t)) := by
  classical
  apply petrial_nullity_poly_iso
  exact {
    toEquiv := Equiv.subtypeSubtypeEquivSubtypeInter (· ∈ s) (· ∈ t)
    map_rel_iff' := by rfl
  }
See it in the graphDiscuss this resultChallenge it