digraph_is_alternating_orientation_reversal
The reversal of an alternating orientation of a graph for a rotation system σ is also an alternating orientation for σ.
Statement
theorem digraph_is_alternating_orientation_reversal {V : Type*} (G : SimpleGraph V) (σ : Equiv.Perm G.Dart) (D : Digraph V) (hD : digraph_is_alternating_orientation G σ D) : digraph_is_alternating_orientation G σ ⟨fun u v => D.Adj v u⟩
- Source
- step towards three_connected_plane_eulerian_arborescence_minimizers_alternating
- Verified
- 28 Oct 2026
- Axioms
Quot.soundpropext- Built on 2
- digraph_is_alternating_orientationFor 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…
- 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…
The proof, explained
To show that reversing the edges of an alternating orientation D yields another alternating orientation, we verify the orientation axioms and the alternating condition along the rotation permutation σ. The reversal inherits edge coverage and irreflexivity directly from D by the symmetry of undirected adjacency. For alternation, since exactly one orientation of each edge is present in an orientation, a dart belongs to the reversed digraph if and only if it does not belong to D; applying this equivalence to both a dart d and its successor σ(d) transforms the alternating property of D into that of the reversal.
The problem reduces to showing that the reversed digraph is an orientation of G and that it satisfies the alternating condition along σ.
We decompose the hypothesis hD into its constituent properties: that D covers all edges of G (hor), that D contains no bidirectional edges (hirr), and that D alternates along the dart permutation σ (halt). By definition of an alternating orientation, it suffices to show that the reversal ⟨fun u v => D.Adj v u⟩ is an orientation of G and that it alternates along σ.
obtain ⟨⟨hor, hirr⟩, halt⟩ := hD constructor
The reversed digraph satisfies the edge coverage condition of an orientation.
We split the orientation condition into edge coverage and irreflexivity. For any vertices u and v, the reversed digraph has an edge between them in one direction or the other if and only if D(v, u) ∨ D(u, v). By commutativity of disjunction (or_comm), this is equivalent to D(u, v) ∨ D(v, u), which holds if and only if u and v are adjacent in G by the coverage property (hor) of D.
uses
or_comm· constructor · intro u v exact or_comm.trans (hor u v)
The reversed digraph is irreflexive, containing no bidirectional edges.
For any vertices u and v, having directed edges in both directions in the reversal would require both D(v, u) and D(u, v) to hold. This is ruled out directly by the irreflexivity property (hirr) of D evaluated at v and u.
· intro u v exact hirr v u
For every dart e of G, the reversed edge is in D if and only if the forward edge is not.
To prove alternation, we fix an arbitrary dart d of G and first establish a general lemma (key): for any dart e, D contains the reverse edge (e.2, e.1) if and only if it does not contain the forward edge (e.1, e.2). Because e is an edge of G, coverage (hor) guarantees that D contains at least one of the two directions (h1), while irreflexivity (hirr) prevents it from containing both (h2). If the reverse edge is present, the forward edge cannot be present by h2. Conversely, if the forward edge is absent, then between the two branches of h1, the forward branch is ruled out by contradiction (absurd), leaving the reverse edge present.
uses
absurd· intro d have key : ∀ e : G.Dart, D.Adj e.toProd.2 e.toProd.1 ↔ ¬ D.Adj e.toProd.1 e.toProd.2 := by intro e have h1 : D.Adj e.toProd.1 e.toProd.2 ∨ D.Adj e.toProd.2 e.toProd.1 := (hor e.toProd.1 e.toProd.2).mpr e.adj have h2 : ¬ (D.Adj e.toProd.1 e.toProd.2 ∧ D.Adj e.toProd.2 e.toProd.1) := hirr e.toProd.1 e.toProd.2 constructor · intro h h'; exact h2 ⟨h', h⟩ · intro h rcases h1 with h' | h' · exact absurd h' h · exact h'
The reversed digraph satisfies the alternating condition along the rotation permutation σ.
For the chosen dart d, the reversed digraph contains d if and only if D contains the reverse edge (d.2, d.1). By key applied to d, this is equivalent to D not containing d. By the alternation property (halt) of D, not containing d is equivalent to D containing the forward dart σ(d). Finally, by key applied to σ(d), D containing σ(d) is equivalent to the reversed digraph not containing σ(d). Rewriting with these three equivalences completes the proof.
show D.Adj d.toProd.2 d.toProd.1 ↔ ¬ D.Adj (σ d).toProd.2 (σ d).toProd.1 rw [key d, halt d, key (σ d)]
or_comm- Disjunction is commutative: for any propositions a and b, a ∨ b ↔ b ∨ a.
absurd- The principle of explosion: from a proposition a and its negation ¬a, any proposition follows.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The reversal of an alternating orientation of a graph for a rotation system σ is also an alternating orientation for σ. -/theorem digraph_is_alternating_orientation_reversal {V : Type*} (G : SimpleGraph V) (σ : Equiv.Perm G.Dart) (D : Digraph V) (hD : digraph_is_alternating_orientation G σ D) : digraph_is_alternating_orientation G σ ⟨fun u v => D.Adj v u⟩ := by obtain ⟨⟨hor, hirr⟩, halt⟩ := hD constructor · constructor · intro u v exact or_comm.trans (hor u v) · intro u v exact hirr v u · intro d have key : ∀ e : G.Dart, D.Adj e.toProd.2 e.toProd.1 ↔ ¬ D.Adj e.toProd.1 e.toProd.2 := by intro e have h1 : D.Adj e.toProd.1 e.toProd.2 ∨ D.Adj e.toProd.2 e.toProd.1 := (hor e.toProd.1 e.toProd.2).mpr e.adj have h2 : ¬ (D.Adj e.toProd.1 e.toProd.2 ∧ D.Adj e.toProd.2 e.toProd.1) := hirr e.toProd.1 e.toProd.2 constructor · intro h h'; exact h2 ⟨h', h⟩ · intro h rcases h1 with h' | h' · exact absurd h' h · exact h' show D.Adj d.toProd.2 d.toProd.1 ↔ ¬ D.Adj (σ d).toProd.2 (σ d).toProd.1 rw [key d, halt d, key (σ d)]