petersen_graph_edgeFinset_card
The Petersen graph petersen_graph has 15 edges (its edgeFinset, with adjacency decided by Disjoint, has card 15).
Statement
theorem petersen_graph_edgeFinset_card : letI : DecidableRel petersen_graph.Adj := fun s t => inferInstanceAs (Decidable (Disjoint s.1 t.1)) petersen_graph.edgeFinset.card = 15
- Source
- Sanity check of petersen_graph (P10 has 15 edges), 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 is modeled with vertices as the 2-element subsets of a 5-element set and edges between disjoint pairs. Because the vertex type is finite and adjacency is decidable, the full graph and its edge set are finite and computationally concrete. The proof verifies the claim that the graph has 15 edges by direct computation (`decide`).
The Petersen graph has exactly 15 edges. automation
Since the vertex type consists of the 2-element subsets of a 5-element set and adjacency is decidable (given by disjointness of finite sets), the edge finset is completely computable. The `decide` tactic evaluates the cardinality of the edge set by exhaustive finite computation and confirms it equals 15.
decide
- The proof relies entirely on computational reflection via `decide` rather than an algebraic argument: Lean evaluates the finite vertex set of $\binom{5}{2} = 10$ vertices, identifies all pairs of disjoint 2-element subsets, and counts the resulting 15 undirected edges.
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_edgeFinset_card : letI : DecidableRel petersen_graph.Adj := fun s t => inferInstanceAs (Decidable (Disjoint s.1 t.1)) petersen_graph.edgeFinset.card = 15 := by decide