petersen_graph_incidenceSet_ncard
The Petersen graph is cubic: every vertex x of petersen_graph lies in exactly 3 edges, (petersen_graph.incidenceSet x).ncard = 3.
Statement
theorem petersen_graph_incidenceSet_ncard (x : {s : Finset (Fin 5) // s.card = 2}) :
(petersen_graph.incidenceSet x).ncard = 3- Source
- Sanity check of petersen_graph (P10 is cubic), for arXiv:2610.35794 (Computational complexity of the H-coloring problem in cubic graphs)
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- petersen_graphThe Petersen graph P10, as the Kneser graph K(5,2): a SimpleGraph on the vertex type {s : Finset (Fin 5) // s.card = 2} of 2-element…
The proof, explained
The Petersen graph has vertices as 2-element subsets of a 5-element set, with edges connecting disjoint pairs. To prove that each vertex x is incident to exactly 3 edges, the proof first uses the canonical bijection between incident edges and neighbors to reduce the problem to counting neighbors of x. Since adjacency means being disjoint, the neighbors of x correspond bijectively to the 2-element subsets of the complement of x's underlying 2-set. Because the complement has 5 - 2 = 3 elements, the number of such subsets is (3 choose 2) = 3.
The number of edges incident to x equals the number of neighbors of x.
In any simple graph, the edges incident to a vertex x are canonically in bijection with the neighbors of x via SimpleGraph.incidenceSetEquivNeighborSet. By rewriting set cardinalities to subtype cardinals with Nat.card_coe_set_eq and applying Nat.card_congr across this bijection, we find that the incidence set and the neighbor set have the same cardinality, so it suffices to show that x has 3 neighbors.
uses
Nat.card_coe_set_eq,Nat.card_congr,SimpleGraph.incidenceSetEquivNeighborSetclassical -- the incidence set of `x` is in bijection with its neighbour set have h1 : (petersen_graph.incidenceSet x).ncard = (petersen_graph.neighborSet x).ncard := by rw [← Nat.card_coe_set_eq, ← Nat.card_coe_set_eq] exact Nat.card_congr (SimpleGraph.incidenceSetEquivNeighborSet petersen_graph x) rw [h1]
The set cardinality of the neighbor set equals the cardinality of the neighbor subtype as a finite type.
Rewriting using Nat.card_coe_set_eq and Nat.card_eq_fintype_card converts the set cardinal `ncard` into `Fintype.card` of the subtype of neighbors of x.
uses
Nat.card_coe_set_eq,Nat.card_eq_fintype_cardhave h2 : (petersen_graph.neighborSet x).ncard = Fintype.card ↥(petersen_graph.neighborSet x) := by rw [← Nat.card_coe_set_eq, Nat.card_eq_fintype_card] rw [h2]
Let s be the 2-element subset of Fin 5 representing vertex x.
Vertices of the Petersen graph are defined as pairs consisting of a subset s ⊆ Fin 5 together with a proof that its cardinality is 2. We name this subset s and note that s.card = 2.
set s : Finset (Fin 5) := x.1 have hscard : s.card = 2 := x.2
The neighbors of x are in bijection with the 2-element subsets of the complement sᶜ.
In the Petersen graph, two vertices are adjacent if and only if their underlying 2-element subsets are disjoint. A subset is disjoint from s if and only if it is contained in the complement sᶜ (by Finset.disjoint_left and Finset.mem_compl). Thus, sending a neighbor to its underlying set yields a 2-element subset of sᶜ (using Finset.mem_powersetCard and Finset.disjoint_left.mp), and conversely, any 2-element subset of sᶜ is disjoint from s and yields a neighbor of x (using Finset.mem_powersetCard.mp). These assignments are mutually inverse, defining an equivalence e.
uses
Finset.mem_powersetCard,Finset.mem_compl,Finset.disjoint_left.mp,Finset.mem_powersetCard.mp,Finset.disjoint_lefthave e : ↥(petersen_graph.neighborSet x) ≃ ↥((sᶜ).powersetCard 2) := { toFun := fun t : ↥(petersen_graph.neighborSet x) => (⟨t.1.1, by rw [Finset.mem_powersetCard] refine ⟨fun a ha => ?_, t.1.2⟩ rw [Finset.mem_compl] intro hsa exact Finset.disjoint_left.mp t.2 hsa ha⟩ : ↥((sᶜ).powersetCard 2)) invFun := fun u : ↥((sᶜ).powersetCard 2) => (⟨⟨u.1, (Finset.mem_powersetCard.mp u.2).2⟩, by change Disjoint (s : Finset (Fin 5)) (u.1 : Finset (Fin 5)) rw [Finset.disjoint_left] intro a hsa hau have h : a ∈ sᶜ := (Finset.mem_powersetCard.mp u.2).1 hau rw [Finset.mem_compl] at h exact h hsa⟩ : ↥(petersen_graph.neighborSet x)) left_inv := fun t => rfl right_inv := fun u => rfl }
The number of neighbors is (5 - 2).choose 2 = 3, completing the proof.
Rewriting by Fintype.card_congr with the bijection e replaces the neighbor count by the cardinality of (sᶜ).powersetCard 2. By Finset.card_coe, Finset.card_powersetCard, Finset.card_compl, and s.card = 2, this is ((Fintype.card (Fin 5) - 2).choose 2), which norm_num evaluates to 3.
uses
Fintype.card_congr,Fintype.card_coe,Finset.card_powersetCard,Finset.card_complrw [Fintype.card_congr e, Fintype.card_coe, Finset.card_powersetCard, Finset.card_compl, hscard] norm_num
Nat.card_coe_set_eq- The cardinal `Nat.card` of a set coerced to a subtype equals its set cardinality `ncard`.
Nat.card_congr- If two types are equivalent via a bijection, their cardinals (`Nat.card`) are equal.
SimpleGraph.incidenceSetEquivNeighborSet- In any simple graph, the set of edges incident to a vertex is canonically in bijection with the vertex's set of neighbors.
Nat.card_eq_fintype_card- For any finite type, its cardinal `Nat.card` equals its `Fintype.card`.
Finset.mem_powersetCard- A finite set belongs to `Finset.powersetCard n t` if and only if it is a subset of `t` with cardinality `n`.
Finset.mem_compl- An element belongs to the complement of a finite set if and only if it does not belong to the set.
Finset.disjoint_left.mp- If two finite sets are disjoint, any element belonging to the first does not belong to the second.
Finset.mem_powersetCard.mp- If a finite set belongs to `Finset.powersetCard n t`, it is a subset of `t` and has cardinality `n`.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Fintype.card_congr- If two finite types are equivalent via a bijection, their `Fintype.card` values are equal.
Fintype.card_coe- The cardinality of a finite set coerced to a subtype equals the cardinality of the finite set.
Finset.card_powersetCard- The number of `n`-element subsets of a finite set `s` is `s.card.choose n`.
Finset.card_compl- The cardinality of the complement of a subset `s` in a finite universe `α` is `Fintype.card α - s.card`.
- Classical logic (`classical`) is assumed to ensure decidability of equality and set membership throughout the proof.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem petersen_graph_incidenceSet_ncard (x : {s : Finset (Fin 5) // s.card = 2}) : (petersen_graph.incidenceSet x).ncard = 3 := by classical -- the incidence set of `x` is in bijection with its neighbour set have h1 : (petersen_graph.incidenceSet x).ncard = (petersen_graph.neighborSet x).ncard := by rw [← Nat.card_coe_set_eq, ← Nat.card_coe_set_eq] exact Nat.card_congr (SimpleGraph.incidenceSetEquivNeighborSet petersen_graph x) rw [h1] have h2 : (petersen_graph.neighborSet x).ncard = Fintype.card ↥(petersen_graph.neighborSet x) := by rw [← Nat.card_coe_set_eq, Nat.card_eq_fintype_card] rw [h2] set s : Finset (Fin 5) := x.1 have hscard : s.card = 2 := x.2 -- a vertex `t` is a neighbour of `x` iff `t.1 ⊆ sᶜ`, i.e. `t.1 ∈ (sᶜ).powersetCard 2` have e : ↥(petersen_graph.neighborSet x) ≃ ↥((sᶜ).powersetCard 2) := { toFun := fun t : ↥(petersen_graph.neighborSet x) => (⟨t.1.1, by rw [Finset.mem_powersetCard] refine ⟨fun a ha => ?_, t.1.2⟩ rw [Finset.mem_compl] intro hsa exact Finset.disjoint_left.mp t.2 hsa ha⟩ : ↥((sᶜ).powersetCard 2)) invFun := fun u : ↥((sᶜ).powersetCard 2) => (⟨⟨u.1, (Finset.mem_powersetCard.mp u.2).2⟩, by change Disjoint (s : Finset (Fin 5)) (u.1 : Finset (Fin 5)) rw [Finset.disjoint_left] intro a hsa hau have h : a ∈ sᶜ := (Finset.mem_powersetCard.mp u.2).1 hau rw [Finset.mem_compl] at h exact h hsa⟩ : ↥(petersen_graph.neighborSet x)) left_inv := fun t => rfl right_inv := fun u => rfl } rw [Fintype.card_congr e, Fintype.card_coe, Finset.card_powersetCard, Finset.card_compl, hscard] norm_num