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
- 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…
- petrial_nullity_poly_disjoint_finset_unionIf disjoint finite vertex sets have no edges between them, the nullity polynomial on their union is the product of the nullity polynomials…
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 }