digraph_alternating_orientation_unique_up_to_reversal
On any connected graph with a rotation system σ, an alternating orientation is uniquely determined up to reversal: any two alternating orientations D₁ and D₂ satisfy D₁ = D₂ or D₁ is the reversal of D₂.
Statement
theorem digraph_alternating_orientation_unique_up_to_reversal {V : Type*} (G : SimpleGraph V) (hG : G.Connected) (σ : Equiv.Perm G.Dart) (hσ : simple_graph_is_rotation_system G σ) (D₁ D₂ : Digraph V) (hD₁ : digraph_is_alternating_orientation G σ D₁) (hD₂ : digraph_is_alternating_orientation G σ D₂) : D₁ = D₂ ∨ ∀ u v, D₁.Adj u v ↔ D₂.Adj v u
- Source
- step towards three_connected_plane_eulerian_arborescence_minimizers_alternating
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- digraph_ext_iffTwo digraphs on the same vertex type are equal if and only if their adjacency relations are logically equivalent.
- 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…
- 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…
- 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 prove that two alternating orientations D₁ and D₂ are either identical or reversals of one another, we consider the predicate A(d) stating that D₁ and D₂ agree on the direction of a dart d. Because alternating orientations flip direction under each application of the vertex rotation σ, the agreement predicate is invariant under σ, and therefore constant across all darts emanating from the same vertex. Furthermore, because valid orientations choose exactly one direction per edge, agreement is invariant under dart reversal, which allows it to propagate across edges and along walks. Since the graph is connected, the agreement status is identical across all darts in the graph, meaning D₁ and D₂ either agree everywhere (D₁ = D₂) or disagree everywhere (D₁ is the reversal of D₂).
Define the agreement predicate A(d) on darts, asserting that D₁ and D₂ orient the dart d in the same direction.
We introduce classical reasoning and define A(d) to hold if and only if D₁ contains the directed edge d.toProd if and only if D₂ contains d.toProd.
classical let A : G.Dart → Prop := fun d => (D₁.Adj d.toProd.1 d.toProd.2 ↔ D₂.Adj d.toProd.1 d.toProd.2)
Agreement on a dart is invariant under the rotation system: A(σ(d)) ↔ A(d) for every dart d.
By the definition of an alternating orientation, applying the rotation σ reverses the orientation of the dart in both D₁ and D₂: D₁(σ(d)) ↔ ¬D₁(d) and D₂(σ(d)) ↔ ¬D₂(d). Because negating both sides of an equivalence preserves the equivalence, D₁ and D₂ agree on σ(d) if and only if they agree on d.
have hAσ : ∀ d : G.Dart, A (σ d) ↔ A d := by intro d dsimp only [A] have h1 := hD₁.2 d have h2 := hD₂.2 d tauto
Agreement on a dart is invariant under any integer power of the rotation: A(σⁱ(d)) ↔ A(d) for all i ∈ ℤ.
We perform two-sided induction on i ∈ ℤ using zpow_induction_right. The base case i = 0 is immediate, while multiplication by σ and σ⁻¹ preserves the invariance property by rewriting the permutation composition with Equiv.Perm.mul_apply and using the one-step invariance of σ.
uses
zpow_induction_right,Equiv.Perm.mul_applyhave hApow : ∀ (i : ℤ) (d : G.Dart), A ((σ ^ i) d) ↔ A d := by have key : ∀ (a : Equiv.Perm G.Dart), (∀ d, A (a d) ↔ A d) → ∀ d, A ((a * σ) d) ↔ A d := by intro a ha d rw [Equiv.Perm.mul_apply] exact (ha (σ d)).trans (hAσ d) have keyinv : ∀ (a : Equiv.Perm G.Dart), (∀ d, A (a d) ↔ A d) → ∀ d, A ((a * σ⁻¹) d) ↔ A d := by intro a ha d rw [Equiv.Perm.mul_apply] have hinv : A (σ⁻¹ d) ↔ A d := by have h := (hAσ (σ⁻¹ d)).symm simpa using h exact (ha (σ⁻¹ d)).trans hinv intro i d exact zpow_induction_right (P := fun a => ∀ d, A (a d) ↔ A d) (g := σ) (fun d => by simp) key keyinv i d
Any two darts with the same source vertex have the same agreement status: if d and e start at the same vertex, then A(d) ↔ A(e).
By the definition of a rotation system, σ acts transitively on all darts emanating from any given vertex, so e = σⁱ(d) for some integer power i. Invariance under powers of σ then yields A(d) ↔ A(e).
have hsame : ∀ d e : G.Dart, d.toProd.1 = e.toProd.1 → (A d ↔ A e) := by intro d e hde obtain ⟨i, hi⟩ := hσ.2 d e hde rw [← hi] exact (hApow i d).symm
Agreement is invariant under reversing a dart: A(d⁻¹) ↔ A(d).
Because D₁ and D₂ are valid orientations of G, each edge is oriented in exactly one direction. Thus, for each orientation, (v, u) is directed if and only if (u, v) is not. Reversing the dart negates the condition in both orientations, which preserves their equivalence.
uses
SimpleGraph.Adj.symmhave hrev : ∀ d : G.Dart, A ⟨(d.toProd.2, d.toProd.1), SimpleGraph.Adj.symm d.adj⟩ ↔ A d := by intro d dsimp only [A] have ho1 := (hD₁.1.1 d.toProd.1 d.toProd.2).mpr d.adj have ha1 := hD₁.1.2 d.toProd.1 d.toProd.2 have ho2 := (hD₂.1.1 d.toProd.1 d.toProd.2).mpr d.adj have ha2 := hD₂.1.2 d.toProd.1 d.toProd.2 tauto
Agreement propagates across an edge: if u is adjacent to v in G, then any dart starting at u and any dart starting at v share the same agreement status.
Given an edge between u and v, any dart d starting at u shares its source with the dart (u, v), so A(d) ↔ A(u, v). By reversal, A(u, v) ↔ A(v, u). The reversed dart (v, u) shares its source with any dart e starting at v, so A(v, u) ↔ A(e). Composing these three equivalences gives A(d) ↔ A(e).
uses
SimpleGraph.Adj.symmhave hedge : ∀ {u v : V} (h : G.Adj u v) (d e : G.Dart), d.toProd.1 = u → e.toProd.1 = v → (A d ↔ A e) := by intro u v h d e hd he have h1 : A d ↔ A (⟨(u, v), h⟩ : G.Dart) := hsame d _ (by simpa using hd) have h2 : A (⟨(u, v), h⟩ : G.Dart) ↔ A (⟨(v, u), SimpleGraph.Adj.symm h⟩ : G.Dart) := (hrev ⟨(u, v), h⟩).symm have h3 : A (⟨(v, u), SimpleGraph.Adj.symm h⟩ : G.Dart) ↔ A e := hsame _ e (by simpa using he.symm) exact h1.trans (h2.trans h3)
Agreement propagates along any walk: if there is a walk from u to v, any dart starting at u and any dart starting at v share the same agreement status.
We induct on the walk using SimpleGraph.Walk.rec. For a trivial zero-step walk, both darts originate at the same vertex, which is covered by source agreement. For a walk formed by prepending an edge (u, w) to an existing walk from w to v, we bridge from u to w using the edge-propagation lemma and then apply the induction hypothesis.
uses
SimpleGraph.Walk.rec,SimpleGraph.Adj.symmhave hwalk : ∀ {u v : V} (p : G.Walk u v) (d e : G.Dart), d.toProd.1 = u → e.toProd.1 = v → (A d ↔ A e) := by intro u v p refine SimpleGraph.Walk.rec (motive := fun u v _ => ∀ d e : G.Dart, d.toProd.1 = u → e.toProd.1 = v → (A d ↔ A e)) ?_ ?_ p · intro u d e hd he exact hsame d e (by rw [hd, he]) · intro u w x h p' ih d e hd he have h1 : A d ↔ A (⟨(w, u), SimpleGraph.Adj.symm h⟩ : G.Dart) := hedge h d _ hd rfl have h2 : A (⟨(w, u), SimpleGraph.Adj.symm h⟩ : G.Dart) ↔ A e := ih _ e rfl he exact h1.trans h2
Agreement is global: A(d) ↔ A(e) for all darts d and e in G.
Since G is connected, any two vertices can be joined by a walk, which we obtain via Classical.choice from the preconnectedness hypothesis. Propagating agreement along this walk shows that all darts in G have the same agreement status.
uses
Classical.choicehave hall : ∀ d e : G.Dart, A d ↔ A e := by intro d e exact hwalk (Classical.choice (hG.preconnected d.toProd.1 e.toProd.1)) d e rfl rfl
If G has at least one dart d₀ and D₁ agrees with D₂ on d₀, then D₁ = D₂.
Global agreement implies that A(d) holds for every dart d. By digraph_ext_iff, it suffices to check edge agreement between all pairs of vertices u and v. For adjacent vertices, agreement on the dart (u, v) shows D₁.Adj u v ↔ D₂.Adj u v. For non-adjacent vertices, neither digraph can contain an edge because any directed edge would force an underlying edge in G via Or.inl. Therefore, D₁ = D₂.
uses
digraph_ext_iff,Or.inlby_cases hne : Nonempty G.Dart · obtain ⟨d0⟩ := hne by_cases hb : A d0 · left apply (digraph_ext_iff D₁ D₂).mpr intro u v by_cases huv : G.Adj u v · have hd : A (⟨(u, v), huv⟩ : G.Dart) := (hall _ d0).mpr hb simpa using hd · have h1 : ¬ D₁.Adj u v := by intro h exact huv ((hD₁.1.1 u v).mp (Or.inl h)) have h2 : ¬ D₂.Adj u v := by intro h exact huv ((hD₂.1.1 u v).mp (Or.inl h)) tauto
If G has at least one dart d₀ and D₁ disagrees with D₂ on d₀, then D₁ is the reversal of D₂.
Global agreement implies that A(d) fails for every dart d, so D₁ and D₂ disagree on every edge of G. For adjacent u and v, since D₂ contains exactly one of (u, v) or (v, u), disagreeing on (u, v) means D₁.Adj u v ↔ D₂.Adj v u. For non-adjacent vertices, neither digraph can have an edge in either direction, using the symmetry of adjacency (SimpleGraph.adj_comm). Hence D₁ is the reversal of D₂.
uses
Or.inl,SimpleGraph.adj_comm· right intro u v by_cases huv : G.Adj u v · have hd : ¬ A (⟨(u, v), huv⟩ : G.Dart) := fun hA => hb ((hall _ d0).mp hA) have hd' : ¬ (D₁.Adj u v ↔ D₂.Adj u v) := hd have ho2 := (hD₂.1.1 u v).mpr huv have ha2 := hD₂.1.2 u v tauto · have h1 : ¬ D₁.Adj u v := by intro h exact huv ((hD₁.1.1 u v).mp (Or.inl h)) have huv' : ¬ G.Adj v u := by intro h exact huv ((SimpleGraph.adj_comm G u v).mpr h) have h2 : ¬ D₂.Adj v u := by intro h exact huv' ((hD₂.1.1 v u).mp (Or.inl h)) tauto
If G has no darts, then D₁ = D₂ vacuously.
If G contains no darts, it has no edges. Since any directed edge in D₁ or D₂ would witness an edge in G via Or.inl, both digraphs must be empty. By digraph_ext_iff, D₁ = D₂.
uses
digraph_ext_iff,Or.inl· left apply (digraph_ext_iff D₁ D₂).mpr intro u v have h1 : ¬ D₁.Adj u v := by intro h exact hne ⟨⟨(u, v), ((hD₁.1.1 u v).mp (Or.inl h))⟩⟩ have h2 : ¬ D₂.Adj u v := by intro h exact hne ⟨⟨(u, v), ((hD₂.1.1 u v).mp (Or.inl h))⟩⟩ tauto
Equiv.Perm.mul_apply- Composition of permutations evaluates by applying the right permutation first and then the left: (f * g)(x) = f(g(x)).
zpow_induction_right- Two-sided induction on integers: if a property holds for the identity and is preserved under multiplying by g and by g⁻¹, then it holds for g^n for all n ∈ ℤ.
SimpleGraph.Adj.symm- Adjacency in a simple graph is symmetric: if u is adjacent to v, then v is adjacent to u.
SimpleGraph.Walk.rec- Induction principle for walks: to prove a statement for all walks in a graph, it suffices to prove it for trivial (zero-step) walks and show it is preserved when prepending an edge.
Classical.choice- The axiom of choice: extracts an element from any nonempty type.
digraph_ext_iff- Two directed graphs on the same vertex type are equal if and only if they have the same directed edges.
Or.inl- Left introduction rule for disjunction: from P, deduce P ∨ Q.
SimpleGraph.adj_comm- Adjacency is commutative: u is adjacent to v if and only if v is adjacent to u.
- When the graph has no darts (an isolated single vertex or empty graph), the theorem holds vacuously because both orientations are necessarily empty; Lean handles this as a separate case split at the end.
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.
/-- On any connected graph with a rotation system σ, an alternating orientation is uniquely determined up to reversal: any two alternating orientations D₁ and D₂ satisfy D₁ = D₂ or D₁ is the reversal of D₂. -/theorem digraph_alternating_orientation_unique_up_to_reversal {V : Type*} (G : SimpleGraph V) (hG : G.Connected) (σ : Equiv.Perm G.Dart) (hσ : simple_graph_is_rotation_system G σ) (D₁ D₂ : Digraph V) (hD₁ : digraph_is_alternating_orientation G σ D₁) (hD₂ : digraph_is_alternating_orientation G σ D₂) : D₁ = D₂ ∨ ∀ u v, D₁.Adj u v ↔ D₂.Adj v u := by classical let A : G.Dart → Prop := fun d => (D₁.Adj d.toProd.1 d.toProd.2 ↔ D₂.Adj d.toProd.1 d.toProd.2) have hAσ : ∀ d : G.Dart, A (σ d) ↔ A d := by intro d dsimp only [A] have h1 := hD₁.2 d have h2 := hD₂.2 d tauto have hApow : ∀ (i : ℤ) (d : G.Dart), A ((σ ^ i) d) ↔ A d := by have key : ∀ (a : Equiv.Perm G.Dart), (∀ d, A (a d) ↔ A d) → ∀ d, A ((a * σ) d) ↔ A d := by intro a ha d rw [Equiv.Perm.mul_apply] exact (ha (σ d)).trans (hAσ d) have keyinv : ∀ (a : Equiv.Perm G.Dart), (∀ d, A (a d) ↔ A d) → ∀ d, A ((a * σ⁻¹) d) ↔ A d := by intro a ha d rw [Equiv.Perm.mul_apply] have hinv : A (σ⁻¹ d) ↔ A d := by have h := (hAσ (σ⁻¹ d)).symm simpa using h exact (ha (σ⁻¹ d)).trans hinv intro i d exact zpow_induction_right (P := fun a => ∀ d, A (a d) ↔ A d) (g := σ) (fun d => by simp) key keyinv i d have hsame : ∀ d e : G.Dart, d.toProd.1 = e.toProd.1 → (A d ↔ A e) := by intro d e hde obtain ⟨i, hi⟩ := hσ.2 d e hde rw [← hi] exact (hApow i d).symm have hrev : ∀ d : G.Dart, A ⟨(d.toProd.2, d.toProd.1), SimpleGraph.Adj.symm d.adj⟩ ↔ A d := by intro d dsimp only [A] have ho1 := (hD₁.1.1 d.toProd.1 d.toProd.2).mpr d.adj have ha1 := hD₁.1.2 d.toProd.1 d.toProd.2 have ho2 := (hD₂.1.1 d.toProd.1 d.toProd.2).mpr d.adj have ha2 := hD₂.1.2 d.toProd.1 d.toProd.2 tauto have hedge : ∀ {u v : V} (h : G.Adj u v) (d e : G.Dart), d.toProd.1 = u → e.toProd.1 = v → (A d ↔ A e) := by intro u v h d e hd he have h1 : A d ↔ A (⟨(u, v), h⟩ : G.Dart) := hsame d _ (by simpa using hd) have h2 : A (⟨(u, v), h⟩ : G.Dart) ↔ A (⟨(v, u), SimpleGraph.Adj.symm h⟩ : G.Dart) := (hrev ⟨(u, v), h⟩).symm have h3 : A (⟨(v, u), SimpleGraph.Adj.symm h⟩ : G.Dart) ↔ A e := hsame _ e (by simpa using he.symm) exact h1.trans (h2.trans h3) have hwalk : ∀ {u v : V} (p : G.Walk u v) (d e : G.Dart), d.toProd.1 = u → e.toProd.1 = v → (A d ↔ A e) := by intro u v p refine SimpleGraph.Walk.rec (motive := fun u v _ => ∀ d e : G.Dart, d.toProd.1 = u → e.toProd.1 = v → (A d ↔ A e)) ?_ ?_ p · intro u d e hd he exact hsame d e (by rw [hd, he]) · intro u w x h p' ih d e hd he have h1 : A d ↔ A (⟨(w, u), SimpleGraph.Adj.symm h⟩ : G.Dart) := hedge h d _ hd rfl have h2 : A (⟨(w, u), SimpleGraph.Adj.symm h⟩ : G.Dart) ↔ A e := ih _ e rfl he exact h1.trans h2 have hall : ∀ d e : G.Dart, A d ↔ A e := by intro d e exact hwalk (Classical.choice (hG.preconnected d.toProd.1 e.toProd.1)) d e rfl rfl by_cases hne : Nonempty G.Dart · obtain ⟨d0⟩ := hne by_cases hb : A d0 · left apply (digraph_ext_iff D₁ D₂).mpr intro u v by_cases huv : G.Adj u v · have hd : A (⟨(u, v), huv⟩ : G.Dart) := (hall _ d0).mpr hb simpa using hd · have h1 : ¬ D₁.Adj u v := by intro h exact huv ((hD₁.1.1 u v).mp (Or.inl h)) have h2 : ¬ D₂.Adj u v := by intro h exact huv ((hD₂.1.1 u v).mp (Or.inl h)) tauto · right intro u v by_cases huv : G.Adj u v · have hd : ¬ A (⟨(u, v), huv⟩ : G.Dart) := fun hA => hb ((hall _ d0).mp hA) have hd' : ¬ (D₁.Adj u v ↔ D₂.Adj u v) := hd have ho2 := (hD₂.1.1 u v).mpr huv have ha2 := hD₂.1.2 u v tauto · have h1 : ¬ D₁.Adj u v := by intro h exact huv ((hD₁.1.1 u v).mp (Or.inl h)) have huv' : ¬ G.Adj v u := by intro h exact huv ((SimpleGraph.adj_comm G u v).mpr h) have h2 : ¬ D₂.Adj v u := by intro h exact huv' ((hD₂.1.1 v u).mp (Or.inl h)) tauto · left apply (digraph_ext_iff D₁ D₂).mpr intro u v have h1 : ¬ D₁.Adj u v := by intro h exact hne ⟨⟨(u, v), ((hD₁.1.1 u v).mp (Or.inl h))⟩⟩ have h2 : ¬ D₂.Adj u v := by intro h exact hne ⟨⟨(u, v), ((hD₂.1.1 u v).mp (Or.inl h))⟩⟩ tauto