AFTD Auto-Formalizing Theoretical Domains

petrial_matrix_rank_le_card

theoremverified

For any finite simple graph G and any subset F of vertices, the rank of the petrial matrix of G and F over ZMod 2 is at most the number of vertices.

Statement

theorem petrial_matrix_rank_le_card
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (F : Finset V) :
    (petrial_matrix G F).rank ≤ Fintype.card V
Source
step towards op_1239_max_degree_three_tree_petrial_log_concave
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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

Lean source view module on GitHub

/-- For any finite simple graph G and subset F, the rank of petrial_matrix G F is at most |V|. -/
theorem petrial_matrix_rank_le_card
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (F : Finset V) :
    (petrial_matrix G F).rank ≤ Fintype.card V := Matrix.rank_le_card_width _
See it in the graphDiscuss this resultChallenge it