petrial_nullity_poly_singleton_induced
theoremverified
The partial Petrial nullity generating polynomial of the graph induced on one vertex is one plus X.
Statement
theorem petrial_nullity_poly_singleton_induced {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : petrial_nullity_poly (G.induce ({v} : Set V)) = 1 + Polynomial.X
- Source
- Singleton 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
- petrial_nullity_poly_card_one_finsetFor every finite vertex set of cardinality one, the partial Petrial nullity polynomial of the induced graph is one plus X.
Lean source view module on GitHub
open Matrix Polynomial set_option maxRecDepth 10000 set_option maxHeartbeats 0 theorem petrial_nullity_poly_singleton_induced {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : petrial_nullity_poly (G.induce ({v} : Set V)) = 1 + Polynomial.X := by classical let S : Set V := {v} let a : S := ⟨v, rfl⟩ letI : Unique S := { default := a uniq := by intro x; apply Subtype.ext; exact x.2 } have hcard : Fintype.card S = 1 := Fintype.card_unique have hF : (Finset.univ : Finset (Finset S)) = {∅, Finset.univ} := by ext F simp only [Finset.mem_univ, Finset.mem_insert, Finset.mem_singleton, true_iff] by_cases h : a ∈ F · right ext y have hy : y = a := Subsingleton.elim _ _ subst y constructor · intro _; exact Finset.mem_univ _ · intro _; exact h · left ext y have hy : y = a := Subsingleton.elim _ _ subst y simp [h] have hne : (∅ : Finset S) ≠ Finset.univ := by intro h have hmem : a ∈ (∅ : Finset S) := h ▸ Finset.mem_univ a simpa using hmem have hM0 : petrial_matrix (G.induce S) (∅ : Finset S) = 0 := by ext i j have hij : i = j := Subsingleton.elim _ _ subst j simp [petrial_matrix] have hM1 : petrial_matrix (G.induce S) (Finset.univ : Finset S) = 1 := by ext i j have hij : i = j := Subsingleton.elim _ _ subst j simp [petrial_matrix, Subsingleton.elim i (default : S)] unfold petrial_nullity_poly change (∑ F : Finset S, (Polynomial.X : Polynomial ℕ) ^ (Fintype.card S - (petrial_matrix (G.induce S) F).rank)) = _ rw [hF] rw [Finset.sum_insert (by simpa using hne), Finset.sum_singleton, hM0, hM1, Matrix.rank_zero, Matrix.rank_one, hcard] norm_num [add_comm]