digraph_is_alternating_orientation
For a simple graph G, a permutation σ : Equiv.Perm G.Dart of the darts of G (in use, a rotation system: the cyclic order of darts around each vertex) and a digraph D on the same vertex type, D is an alternating orientation for σ: is_graph_orientation G D holds, and for every dart d = (u, w) of G, D has the arc u → w iff D does not have the arc along the dart σ d, so consecutive darts around each vertex point opposite ways and incoming and outgoing arcs alternate.
Statement
def digraph_is_alternating_orientation {V : Type*} (G : SimpleGraph V) (σ : Equiv.Perm G.Dart) (D : Digraph V) : Prop
- Defined in
- arXiv:2610.25886 (Extremal arborescences in graph orientations), Sec. 1 and Thm 1.1 (alternating orientations of plane Eulerian graphs)
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 1
- is_graph_orientationA digraph D is an orientation of a simple graph G if every edge of G is assigned exactly one direction in D, and non-adjacent pairs in G…
- Used by 3
- 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…
- digraph_is_alternating_orientation_reversalThe reversal of an alternating orientation of a graph for a rotation system σ is also an alternating orientation for σ.
Read back from the Lean
The proposition that a directed graph D is an "alternating orientation" of a simple graph G with respect to a dart permutation σ of G. Specifically, it asserts the conjunction of two conditions:
1. D is an orientation of G:
- for all vertices u, v : V, there is a directed edge from u to v or from v to u in D if and only if u and v are adjacent in G, and
- for all vertices u, v : V, D does not have both a directed edge from u to v and from v to u.
2. For every dart d of G (an ordered pair of vertices (d.fst, d.snd) with G.Adj d.fst d.snd), D has a directed edge from d.fst to d.snd if and only if D does not have a directed edge from (σ d).fst to (σ d).snd.
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
/-- D is alternating for σ: at each vertex, consecutive darts in the rotation have opposite directions. -/ def digraph_is_alternating_orientation {V : Type*} (G : SimpleGraph V) (σ : Equiv.Perm G.Dart) (D : Digraph V) : Prop := is_graph_orientation G D ∧ ∀ d : G.Dart, (D.Adj d.fst d.snd ↔ ¬ D.Adj (σ d).fst (σ d).snd)