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
- petrial_coeff_eq_zero_of_gt_cardFor any finite simple graph G and any integer k strictly greater than the number of vertices, petrial_coeff G k equals 0.
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 _