AFTD Auto-Formalizing Theoretical Domains

digraph_alternating_orientation_unique_up_to_reversal

theoremverified

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₂).

  1. 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.

    lines 9–11

      classical
      let A : G.Dart → Prop := fun d =>
        (D₁.Adj d.toProd.1 d.toProd.2 ↔ D₂.Adj d.toProd.1 d.toProd.2)
  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.

    lines 12–17

      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
  3. 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 σ.

    lines 18–34

    uses zpow_induction_right, Equiv.Perm.mul_apply

      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
  4. 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).

    lines 35–39

      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
  5. 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.

    lines 40–48

    uses SimpleGraph.Adj.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
  6. 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).

    lines 49–57

    uses SimpleGraph.Adj.symm

      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)
  7. 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.

    lines 58–68

    uses SimpleGraph.Walk.rec, SimpleGraph.Adj.symm

      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
  8. 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.

    lines 69–71

    uses Classical.choice

      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
  9. 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₂.

    lines 72–87

    uses digraph_ext_iff, Or.inl

      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
  10. 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₂.

    lines 88–105

    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
  11. 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₂.

    lines 106–115

    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.

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

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