AFTD Auto-Formalizing Theoretical Domains

petrial_nullity_poly_iso

theoremverified

Isomorphic finite simple graphs have the same partial Petrial nullity generating polynomial.

Statement

theorem petrial_nullity_poly_iso {V W : Type*} [Fintype V] [Fintype W] [DecidableEq V] [DecidableEq W] (G : SimpleGraph V) (H : SimpleGraph W) [DecidableRel G.Adj] [DecidableRel H.Adj] (e : G ≃g H) : petrial_nullity_poly G = petrial_nullity_poly H
Source
Graph reindexing helper for the OP-1239 counterexample.
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 6

The proof, explained

The theorem is proved by showing that the sums defining the Petrial nullity polynomials of G and H match term by term under the bijection between vertex subsets induced by the graph isomorphism e : G ≃g H. For each subset F ⊆ V, simultaneous row and column reindexing by e transforms the Petrial matrix of G at F into the Petrial matrix of H at e(F). Because reindexing preserves matrix rank and isomorphic graphs have the same vertex count, the exponents |V| - rank(M_F) match for every subset, establishing equality of the polynomials.

  1. To show the polynomials are equal, it suffices to show that the summand for each vertex subset F ⊆ V equals the summand for its image under e in W.

    Unfolding the definition of the Petrial nullity polynomial expresses both sides as sums over all vertex subsets of X^(|V| - rank(M_F)) and X^(|W| - rank(M_F')), respectively. The graph isomorphism e : V ≃ W induces a bijection on finite subsets via Equiv.finsetCongr. Reindexing the sum on the right-hand side using Fintype.sum_equiv reduces the equality of the two sums to verifying that the corresponding terms match for an arbitrary subset F ⊆ V.

    lines 2–4

    uses Fintype.sum_equiv, Equiv.finsetCongr

      dsimp [petrial_nullity_poly]
      rw [Fintype.sum_equiv (Equiv.finsetCongr (e : V ≃ W))]
      intro F
  2. The vertex sets V and W have the same cardinality: |V| = |W|.

    Because e : V ≃ W is a bijection between the finite types V and W, their cardinalities are equal by Fintype.card_congr.

    line 5

    uses Fintype.card_congr

      have hcard : Fintype.card V = Fintype.card W := Fintype.card_congr (e : V ≃ W)
  3. The Petrial matrix of G at F, when reindexed by the vertex isomorphism e, equals the Petrial matrix of H at the image subset e(F).

    Unfolding the definition of the Petrial matrix, each entry is the sum of an adjacency indicator and a diagonal indicator for membership in the subset. We test entrywise equality at indices i, j ∈ W: the (i, j) entry of the reindexed matrix corresponds to indices e⁻¹(i) and e⁻¹(j) in G. By e.map_adj_iff, e⁻¹(i) and e⁻¹(j) are adjacent in G if and only if i and j are adjacent in H, so the adjacency terms agree. By Finset.mem_map_equiv and injectivity of e⁻¹ (via EmbeddingLike.apply_eq_iff_eq), e⁻¹(i) ∈ F and e⁻¹(i) = e⁻¹(j) are equivalent to i ∈ e(F) and i = j, so the diagonal terms agree as well.

    lines 6–17

    uses Matrix.submatrix_apply, Matrix.add_apply, SimpleGraph.adjMatrix_apply, Matrix.diagonal_apply, Finset.mem_map_equiv, e.map_adj_iff, EmbeddingLike.apply_eq_iff_eq

      have hmat : (Matrix.reindex (e : V ≃ W) (e : V ≃ W)) (petrial_matrix G F) =
          petrial_matrix H (F.map (e : V ≃ W).toEmbedding) := by
        dsimp [petrial_matrix]
        ext i j
        simp only [Matrix.submatrix_apply, Matrix.add_apply, SimpleGraph.adjMatrix_apply, Matrix.diagonal_apply]
        simp only [Finset.mem_map_equiv]
        have h_adj : G.Adj ((e : V ≃ W).symm i) ((e : V ≃ W).symm j) ↔ H.Adj i j := by
          rw [← e.map_adj_iff]
          simp
        simp only [h_adj]
        congr 1
        simp only [EmbeddingLike.apply_eq_iff_eq]
  4. The Petrial matrix of H at e(F) has the same rank as the Petrial matrix of G at F.

    Using the previous identity, the Petrial matrix of H at e(F) is obtained from the Petrial matrix of G at F by simultaneous row and column reindexing via e. By Matrix.rank_reindex, reindexing rows and columns preserves matrix rank.

    lines 18–20

    uses Matrix.rank_reindex

      have hrank : (petrial_matrix H (Finset.map (e : V ≃ W).toEmbedding F)).rank =
          (petrial_matrix G F).rank := by
        rw [← hmat, Matrix.rank_reindex]
  5. The summand for F matches the summand for e(F), completing the proof.

    Applying Equiv.finsetCongr_apply rewrites the subset bijection to the embedding map. Substituting |V| = |W| (from hcard) and the rank equality (from hrank) into the exponent X^(|V| - rank(M)) shows that the two terms are identical.

    lines 21–22

    uses Equiv.finsetCongr_apply

      rw [Equiv.finsetCongr_apply]
      rw [hcard, hrank]
EmbeddingLike.apply_eq_iff_eq
Applying an injective map to two elements yields equal results if and only if the two elements are equal.
Equiv.finsetCongr
An equivalence between two types induces a bijection between their types of finite subsets.
Equiv.finsetCongr_apply
Evaluating the subset equivalence induced by e on a finite set s produces the image of s under e viewed as an embedding.
Finset.mem_map_equiv
An element b belongs to the image of a finite set s under an equivalence f if and only if f⁻¹(b) belongs to s.
Fintype.card_congr
Equivalent finite types have the same cardinality.
Fintype.sum_equiv
A sum over a finite index type can be reindexed along an equivalence with another finite type, provided the terms match under the bijection.
Matrix.add_apply
The (i, j) entry of the sum of two matrices is the sum of their (i, j) entries.
Matrix.diagonal_apply
The (i, j) entry of a diagonal matrix is the diagonal element at i if i = j, and 0 otherwise.
Matrix.rank_reindex
Reindexing the rows and columns of a matrix by bijections preserves its rank.
Matrix.submatrix_apply
The (i, j) entry of a submatrix with row map r and column map c is the (r(i), c(j)) entry of the original matrix.
SimpleGraph.adjMatrix_apply
The (v, w) entry of the adjacency matrix of a graph is 1 if v and w are adjacent, and 0 otherwise.
e.map_adj_iff
A graph isomorphism preserves and reflects adjacency: two vertices in the domain are adjacent if and only if their images in the codomain are adjacent.

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_iso {V W : Type*} [Fintype V] [Fintype W] [DecidableEq V] [DecidableEq W] (G : SimpleGraph V) (H : SimpleGraph W) [DecidableRel G.Adj] [DecidableRel H.Adj] (e : G ≃g H) : petrial_nullity_poly G = petrial_nullity_poly H := by  dsimp [petrial_nullity_poly]  rw [Fintype.sum_equiv (Equiv.finsetCongr (e : V ≃ W))]  intro F  have hcard : Fintype.card V = Fintype.card W := Fintype.card_congr (e : V ≃ W)  have hmat : (Matrix.reindex (e : V ≃ W) (e : V ≃ W)) (petrial_matrix G F) =      petrial_matrix H (F.map (e : V ≃ W).toEmbedding) := by    dsimp [petrial_matrix]    ext i j    simp only [Matrix.submatrix_apply, Matrix.add_apply, SimpleGraph.adjMatrix_apply, Matrix.diagonal_apply]    simp only [Finset.mem_map_equiv]    have h_adj : G.Adj ((e : V ≃ W).symm i) ((e : V ≃ W).symm j) ↔ H.Adj i j := by      rw [← e.map_adj_iff]      simp    simp only [h_adj]    congr 1    simp only [EmbeddingLike.apply_eq_iff_eq]  have hrank : (petrial_matrix H (Finset.map (e : V ≃ W).toEmbedding F)).rank =      (petrial_matrix G F).rank := by    rw [← hmat, Matrix.rank_reindex]  rw [Equiv.finsetCongr_apply]  rw [hcard, hrank]
See it in the graphDiscuss this resultChallenge it