AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_plane_rotation_system

def

For a finite simple graph G and a permutation σ : Equiv.Perm G.Dart of its darts, σ is a plane embedding of G given combinatorially, defined as the conjunction of three conditions: (1) G.Connected; (2) simple_graph_is_rotation_system G σ; and (3) genus 0, i.e. Euler's formula V - E + F = 2 computed in ℤ, with V = Fintype.card V, E = G.edgeFinset.card and F = simple_graph_rotation_face_count G σ. By the rotation principle for embeddings these are exactly the plane embeddings of a connected graph up to orientation-preserving homeomorphism (a graph with no edges has no darts, hence F = 0 here, so the one-vertex graph has none; this degenerate case does not arise for graphs with an edge).

Statement

def simple_graph_is_plane_rotation_system {V : Type*} [Fintype V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (σ : Equiv.Perm G.Dart) : Prop
Defined in
Genus-0 rotation systems = plane embeddings (rotation principle; Graphs on Surfaces, Thm 3.2.4 and Sec. 3.2); the fixed plane embedding of OP-541, arXiv:2610.25886 (Extremal arborescences in graph orientations)
Verified
27 Oct 2026
Axioms
none listed
Built on 2
  • simple_graph_is_rotation_systemA rotation system of G is a permutation σ of the darts (directed edges) of G that fixes the tail of every dart and permutes the darts at…
  • simple_graph_rotation_face_countFor a finite simple graph G (explicit argument) and a permutation σ : Equiv.Perm G.Dart of its darts, the number of faces of σ is the…
Used by 1

Read back from the Lean

Given a finite type V, a simple graph G : SimpleGraph V with decidable adjacency, and a permutation σ : Equiv.Perm G.Dart of the darts of G, simple_graph_is_plane_rotation_system G σ asserts that: 1. G is connected (G.Connected). 2. σ is a rotation system on G: - Every dart d and its image σ d have the same source vertex ((σ d).fst = d.fst). - For all darts d and e, if d and e share the same source vertex (d.fst = e.fst), then d and e belong to the same cycle under σ (σ.SameCycle d e). 3. Euler's planar formula holds: (Fintype.card V : ℤ) - (G.edgeFinset.card : ℤ) + (simple_graph_rotation_face_count G σ : ℤ) = 2, where the face count is the number of orbits (cycles) in G.Dart under the permutation d ↦ σ (d.symm).

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

/-- σ is a plane embedding of the connected graph G: a rotation system with V - E + F = 2. -/
def simple_graph_is_plane_rotation_system {V : Type*} [Fintype V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (σ : Equiv.Perm G.Dart) : Prop :=
  G.Connected ∧ simple_graph_is_rotation_system G σ ∧
    (Fintype.card V : ℤ) - (G.edgeFinset.card : ℤ) + (simple_graph_rotation_face_count G σ : ℤ) = 2
See it in the graphDiscuss this resultChallenge it