simple_graph_is_plane_rotation_system
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
- exists_plane_rotation_system_complete_fourK_4 has a plane rotation system: 4 vertices, 6 edges, 4 faces (sanity check of simple_graph_is_plane_rotation_system).
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