simple_graph_is_rotation_system
A 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 each vertex in a single cycle: the cyclic order of the edges around each vertex in a 2-cell embedding.
Statement
def simple_graph_is_rotation_system {V : Type*} (G : SimpleGraph V) (σ : Equiv.Perm G.Dart) : Prop
- Defined in
- Combinatorial embeddings / rotation systems (Mohar-Thomassen, Graphs on Surfaces, Sec. 3.2), used to state the plane embedding of OP-541; arXiv:2610.25886 (Extremal arborescences in graph orientations)
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Used by 5
- complete_three_rotation_face_countEvery rotation system of the triangle K_3 has exactly 2 faces (inside and outside), so V - E + F = 3 - 3 + 2 = 2 (sanity check of…
- 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,…
- digraph_alternating_orientation_unique_up_to_reversalOn any connected graph with a rotation system σ, an alternating orientation is uniquely determined up to reversal: any two alternating…
- digraph_is_eulerian_orientation_of_alternatingAn alternating orientation (for any rotation system) is Eulerian: around each vertex σ maps outgoing darts bijectively to incoming ones…
- 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 type V, a simple graph G on V, and a permutation σ of the darts of G (Equiv.Perm G.Dart), simple_graph_is_rotation_system G σ asserts that:
1. For every dart d of G, the source vertex of σ d is equal to the source vertex of d (i.e., (σ d).fst = d.fst); and
2. For any two darts d and e of G, if they have the same source vertex (d.fst = e.fst), then d and e belong to the same cycle under σ (σ.SameCycle d e).
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 rotation system: it keeps each dart's tail and cycles through all darts at each vertex in one cycle. -/ def simple_graph_is_rotation_system {V : Type*} (G : SimpleGraph V) (σ : Equiv.Perm G.Dart) : Prop := (∀ d, (σ d).fst = d.fst) ∧ ∀ d e : G.Dart, d.fst = e.fst → σ.SameCycle d e