AFTD Auto-Formalizing Theoretical Domains

petersen_graph_edgeFinset_card

theoremverified

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`).

  1. 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.

    line 4

      decide

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 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
See it in the graphDiscuss this resultChallenge it