AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_fullerene

def

A simple graph G on Fin n with decidable adjacency and dart permutation σ is a fullerene if G is 3-vertex-connected, every vertex of G has degree 3, σ is a plane rotation system for G, and every dart d has simple_graph_face_length G σ d equal to 5 or 6.

Statement

def simple_graph_is_fullerene {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
    (σ : Equiv.Perm G.Dart) : Prop
Defined in
arXiv:2611.18384 Sec. 1.2, Sec. 5
Verified
16 Nov 2026
Axioms
none listed
Built on 3
  • simple_graph_three_vertex_connectedA simple graph on Fin n is 3-vertex-connected if it has at least 4 vertices and deleting any set of at most 2 vertices leaves a connected…
  • simple_graph_is_plane_rotation_systemFor a finite simple graph G and a permutation σ : Equiv.Perm G.Dart of its darts, σ is a plane embedding of G given combinatorially,…
  • simple_graph_face_lengthGiven a simple graph G on Fin n with decidable adjacency, a permutation σ of G.Dart, and a dart d : G.Dart, simple_graph_face_length G σ d…

Read back from the Lean

Given a natural number $n$, a simple graph $G$ on the vertex set $\mathrm{Fin}(n)$ with decidable adjacency, and a permutation $\sigma$ of the darts (directed edges) of $G$, simple_graph_is_fullerene G σ asserts that all of the following conditions hold: 1. **3-vertex-connectivity**: $n \ge 4$, and for every subset $X$ of vertices ($\mathrm{Fin}(n)$) with $|X| \le 2$, the induced subgraph $G[(\mathrm{Fin}(n) \setminus X)]$ is connected. 2. **3-regularity**: Every vertex $v \in \mathrm{Fin}(n)$ has degree 3 in $G$. 3. **Plane rotation system**: - $G$ is connected; - $\sigma$ is a rotation system on $G$, meaning that for every dart $d$, $\sigma(d)$ has the same source vertex as $d$ ($(\sigma(d)).\mathrm{fst} = d.\mathrm{fst}$), and for any two darts $d, e$ sharing the same source vertex, $d$ and $e$ belong to the same cycle under $\sigma$; - The Euler characteristic formula holds: $n - |E(G)| + F = 2$, where $n = |\mathrm{Fin}(n)|$, $|E(G)|$ is the number of undirected edges of $G$ (G.edgeFinset.card), and $F$ is the number of orbits (equivalence classes under SameCycle) of the face permutation $\rho = \sigma \circ \mathrm{symm}$ acting on the darts of $G$ (where $\mathrm{symm}$ reverses the direction of a dart). 4. **Face lengths**: For every dart $d$ of $G$, the size of the orbit of $d$ under the face permutation $\rho = \sigma \circ \mathrm{symm}$ is equal to either 5 or 6.

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

/-- A fullerene is a 3-connected cubic plane graph with all face lengths 5 or 6. -/
def simple_graph_is_fullerene {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
    (σ : Equiv.Perm G.Dart) : Prop :=
  simple_graph_three_vertex_connected G ∧
  (∀ v : Fin n, G.degree v = 3) ∧
  simple_graph_is_plane_rotation_system G σ ∧
  ∀ d : G.Dart, simple_graph_face_length G σ d = 5 ∨ simple_graph_face_length G σ d = 6
See it in the graphDiscuss this resultChallenge it