AFTD Auto-Formalizing Theoretical Domains

petersen_graph

def

The 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 subsets of Fin 5, in which two vertices s and t are adjacent iff the finsets s.1 and t.1 are disjoint (Disjoint s.1 t.1).

Statement

def petersen_graph : SimpleGraph {s : Finset (Fin 5) // s.card = 2}
Defined in
arXiv:2610.35794 (Computational complexity of the H-coloring problem in cubic graphs), Figure 1: the Petersen graph P10 (here as the Kneser graph K(5,2), which is isomorphic to it)
Verified
30 Oct 2026
Axioms
none listed
Used by 5

Read back from the Lean

petersen_graph is defined as the simple graph whose vertex type is the subtype of 2-element subsets (Finset) of Fin 5 (i.e., {s : Finset (Fin 5) // s.card = 2}), where two vertices s and t are adjacent if and only if their underlying subsets s.1 and t.1 are disjoint.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The Petersen graph as the Kneser graph K(5,2): 2-subsets of Fin 5, adjacent when disjoint. -/
def petersen_graph : SimpleGraph {s : Finset (Fin 5) // s.card = 2} where
  Adj s t := Disjoint s.1 t.1
  symm := ⟨fun _ _ h => Disjoint.symm h⟩
  loopless := ⟨fun s h => by
    have h2 := s.2
    rw [disjoint_self.mp h] at h2
    simp at h2⟩
See it in the graphDiscuss this resultChallenge it