AFTD Auto-Formalizing Theoretical Domains

petrial_nullity_poly_leaf_finset

theoremverified

If 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 that after deleting v and u.

Statement

theorem petrial_nullity_poly_leaf_finset {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (s : Finset V) (v u : V) (hv : v ∈ s) (hu : u ∈ s) (hdeg : (G.induce (s : Set V)).degree ⟨v, hv⟩ = 1) (hedge : G.Adj v u) : petrial_nullity_poly (G.induce (s : Set V)) = petrial_nullity_poly (G.induce ((s.erase v : Finset V) : Set V)) + 2 * petrial_nullity_poly (G.induce (((s.erase v).erase u : Finset V) : Set V))
Source
Leaf-deletion certificate for the OP-1239 candidate.
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_leaf_recFor a finite graph G with a degree-one vertex v whose neighbour is u, the nullity generating polynomial of G equals the nullity generating…
  • petrial_nullity_poly_induce_induceThe nullity polynomial obtained by inducing on s and then on vertices in t equals the polynomial of the graph induced on the intersection…
  • petrial_nullity_poly_isoIsomorphic finite simple graphs have the same partial Petrial nullity generating polynomial.

Lean source view module on GitHub

set_option maxRecDepth 10000
set_option maxHeartbeats 0

theorem petrial_nullity_poly_leaf_finset {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (s : Finset V) (v u : V) (hv : v ∈ s) (hu : u ∈ s) (hdeg : (G.induce (s : Set V)).degree ⟨v, hv⟩ = 1) (hedge : G.Adj v u) : petrial_nullity_poly (G.induce (s : Set V)) = petrial_nullity_poly (G.induce ((s.erase v : Finset V) : Set V)) + 2 * petrial_nullity_poly (G.induce (((s.erase v).erase u : Finset V) : Set V)) := by
  classical
  let S : Set V := (s : Set V)
  let vv : S := ⟨v, hv⟩
  let uu : S := ⟨u, hu⟩
  let e1 : ((G.induce S).induce ({vv}ᶜ : Set S)) ≃g
      G.induce ((s.erase v : Finset V) : Set V) := {
    toEquiv := {
      toFun := fun x => ⟨x.1.1, by
        apply Finset.mem_erase.mpr
        refine ⟨?_, x.1.2⟩
        intro h
        have hsub : x.1 = vv := Subtype.ext h
        exact x.2 (by simpa [hsub])⟩
      invFun := fun x => ⟨⟨x.1, (Finset.mem_erase.mp x.2).2⟩, by
        change (⟨x.1, (Finset.mem_erase.mp x.2).2⟩ : S) ∉ ({vv} : Set S)
        simp only [Set.mem_singleton_iff]
        intro h
        exact (Finset.mem_erase.mp x.2).1 (congrArg Subtype.val h)⟩
      left_inv := by intro x; apply Subtype.ext; apply Subtype.ext; rfl
      right_inv := by intro x; apply Subtype.ext; rfl
    }
    map_rel_iff' := by rfl
  }
  let e2 : ((G.induce S).induce (({uu} ∪ {vv})ᶜ : Set S)) ≃g
      G.induce (((s.erase v).erase u : Finset V) : Set V) := {
    toEquiv := {
      toFun := fun x => ⟨x.1.1, by
        apply Finset.mem_erase.mpr
        constructor
        · intro h
          have hsub : x.1 = uu := Subtype.ext h
          exact x.2 (by simp [hsub])
        · apply Finset.mem_erase.mpr
          constructor
          · intro h
            have hsub : x.1 = vv := Subtype.ext h
            exact x.2 (by simp [hsub])
          · exact x.1.2⟩
      invFun := fun x => ⟨⟨x.1, (Finset.mem_erase.mp (Finset.mem_erase.mp x.2).2).2⟩, by
        change (⟨x.1, (Finset.mem_erase.mp (Finset.mem_erase.mp x.2).2).2⟩ : S) ∉ ({uu} ∪ {vv} : Set S)
        simp only [Set.mem_union, Set.mem_singleton_iff, not_or]
        constructor
        · intro h
          exact (Finset.mem_erase.mp x.2).1 (congrArg Subtype.val h)
        · intro h
          exact (Finset.mem_erase.mp (Finset.mem_erase.mp x.2).2).1 (congrArg Subtype.val h)⟩
      left_inv := by intro x; apply Subtype.ext; apply Subtype.ext; rfl
      right_inv := by intro x; apply Subtype.ext; rfl
    }
    map_rel_iff' := by rfl
  }
  have hadj : (G.induce S).Adj vv uu := hedge
  have h := petrial_nullity_poly_leaf_rec (G.induce S) hdeg hadj
  rw [petrial_nullity_poly_iso _ _ e1, petrial_nullity_poly_iso _ _ e2] at h
  exact h
See it in the graphDiscuss this resultChallenge it