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
- petersen_graph_edgeFinset_cardThe Petersen graph petersen_graph has 15 edges (its edgeFinset, with adjacency decided by Disjoint, has card 15).
- petersen_hard_core_var_per_vertex_eq_polyFor every real activity x, the per-vertex hard-core variance of the Petersen graph hardCoreVarSize petersen_graph (fun _ => x) / 10 equals…
- petersen_graph_incidenceSet_ncardThe Petersen graph is cubic: every vertex x of petersen_graph lies in exactly 3 edges, (petersen_graph.incidenceSet x).ncard = 3.
- petersen_colorable_of_three_edge_colorableIf es is an edge list with edge_list_connected_cubic n es that has a proper 3-edge-coloring c : Fin es.length → Fin 3 (any two distinct…
- petersen_coloring_languageThe P10-coloring decision problem as a language over Bool (Language Bool): the set of words w such that there exist n : ℕ and es : List (ℕ…
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⟩