AFTD Auto-Formalizing Theoretical Domains

digraph_is_alternating_orientation

def

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

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)
See it in the graphDiscuss this resultChallenge it