AFTD Auto-Formalizing Theoretical Domains

digraph_is_eulerian_orientation_of_alternating

theoremverified

An alternating orientation (for any rotation system) is Eulerian: around each vertex σ maps outgoing darts bijectively to incoming ones (sanity check of digraph_is_alternating_orientation).

Statement

theorem digraph_is_eulerian_orientation_of_alternating {n : ℕ} (G : SimpleGraph (Fin n))
    [DecidableRel G.Adj] (σ : Equiv.Perm G.Dart) (hσ : simple_graph_is_rotation_system G σ)
    (D : Digraph (Fin n)) [DecidableRel D.Adj] (hD : digraph_is_alternating_orientation G σ D) :
    digraph_is_eulerian_orientation G D
Source
Sanity lemma for digraph_is_alternating_orientation (OP-541)
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • digraph_is_eulerian_orientationFor a simple graph G and a digraph D on the vertex type Fin n (as for digraph_arborescence_count_at), D is an Eulerian orientation of G:…
  • 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 an alternating orientation is Eulerian, it suffices to verify that every vertex v has matching in-degree and out-degree. At vertex v, the out-degree |T| and in-degree |U| are shown to equal the cardinalities of the outgoing dart set X and incoming dart set Y, respectively, via projection to the target vertex. The rotation permutation σ preserves the source vertex v and, by the alternating hypothesis, bijectively swaps outgoing darts with incoming darts, showing |X| = |Y| and hence |T| = |U|.

  1. To show that D is an Eulerian orientation of G, it suffices to show that for every vertex v, the out-degree equals the in-degree.

    Unfolding the definition of an Eulerian orientation, D must be an orientation of G (which holds by the alternating orientation hypothesis) and each vertex v must have equal in-degree and out-degree in D.

    lines 5–9

      classical
      unfold digraph_is_eulerian_orientation
      refine ⟨hD.1, fun v => ?_⟩
      show (Finset.univ.filter (fun w : Fin n => D.Adj v w)).card
          = (Finset.univ.filter (fun w : Fin n => D.Adj w v)).card
  2. Define the out-neighborhood T, the in-neighborhood U, the set of outgoing darts X, and the set of incoming darts Y at v, together with their membership criteria.

    We define T as the set of vertices w with D.Adj v w, and U as the set of vertices w with D.Adj w v. Similarly, X consists of the darts d originating at v (d.fst = v) oriented outward (D.Adj v d.snd), while Y consists of the darts originating at v that are not oriented outward (¬ D.Adj v d.snd). Membership in X and Y is characterized explicitly by simplifying filter expressions over the universal finset.

    lines 10–17

    uses Finset.mem_filter, Finset.mem_univ, true_and

      set T : Finset (Fin n) := Finset.univ.filter (fun w => D.Adj v w) with hT
      set U : Finset (Fin n) := Finset.univ.filter (fun w => D.Adj w v) with hU
      set X : Finset G.Dart := Finset.univ.filter (fun d => d.fst = v ∧ D.Adj v d.snd) with hX
      set Y : Finset G.Dart := Finset.univ.filter (fun d => d.fst = v ∧ ¬ D.Adj v d.snd) with hY
      have htest : ∀ d : G.Dart, d ∈ X ↔ d.fst = v ∧ D.Adj v d.snd := by
        intro d; rw [hX]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]
      have htestY : ∀ d : G.Dart, d ∈ Y ↔ d.fst = v ∧ ¬ D.Adj v d.snd := by
        intro d; rw [hY]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]
  3. The number of outgoing darts at v equals the out-degree: |X| = |T|.

    Using Finset.card_bij, we show that d ↦ d.snd is a bijection from X to T. It maps into T by definition of X; it is injective because darts in X share the source v and their targets match; and it is surjective because any out-neighbor w ∈ T defines an edge in G, giving a dart from v to w in X via SimpleGraph.dartOfNeighborSet.

    lines 18–29

    uses Finset.card_bij, Finset.mem_filter, Finset.mem_univ, true_and, SimpleGraph.Dart.ext, Prod.ext, Or.inl, SimpleGraph.dartOfNeighborSet

      have h1 : X.card = T.card := by
        apply Finset.card_bij (fun d (_ : d ∈ X) => d.snd)
        · intro d hd
          rw [htest] at hd; rw [hT]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact hd.2
        · intro d1 hd1 d2 hd2 heq
          rw [htest] at hd1 hd2
          exact SimpleGraph.Dart.ext d1 d2 (Prod.ext (hd1.1.trans hd2.1.symm) heq)
        · intro w hw
          rw [hT] at hw; simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw
          refine ⟨G.dartOfNeighborSet v ⟨w, (hD.1.1 v w).mp (Or.inl hw)⟩, ?_, ?_⟩
          · rw [htest]; exact ⟨rfl, by simpa [SimpleGraph.dartOfNeighborSet] using hw⟩
          · rfl
  4. The number of incoming darts at v equals the in-degree: |Y| = |U|.

    Similarly, d ↦ d.snd is a bijection from Y to U. For d ∈ Y, we have G.Adj v d.snd but ¬ D.Adj v d.snd; because D is an orientation, this forces D.Adj d.snd v, so d.snd ∈ U. Injectivity again holds by dart extensionality with common source v, and surjectivity holds because an in-neighbor w ∈ U yields a dart from v to w which cannot be oriented outward (as orientations forbid directed 2-cycles).

    lines 30–47

    uses Finset.card_bij, Finset.mem_filter, Finset.mem_univ, true_and, SimpleGraph.Dart.ext, Prod.ext, Or.inr, SimpleGraph.dartOfNeighborSet

      have h2 : Y.card = U.card := by
        apply Finset.card_bij (fun d (_ : d ∈ Y) => d.snd)
        · intro d hd
          rw [htestY] at hd; rw [hU]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          have hG : G.Adj v d.snd := hd.1 ▸ d.adj
          rcases (hD.1.1 v d.snd).mpr hG with h | h
          · exact absurd h hd.2
          · exact h
        · intro d1 hd1 d2 hd2 heq
          rw [htestY] at hd1 hd2
          exact SimpleGraph.Dart.ext d1 d2 (Prod.ext (hd1.1.trans hd2.1.symm) heq)
        · intro w hw
          rw [hU] at hw; simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw
          refine ⟨G.dartOfNeighborSet v ⟨w, (hD.1.1 v w).mp (Or.inr hw)⟩, ?_, ?_⟩
          · rw [htestY]; refine ⟨rfl, ?_⟩
            simp only [SimpleGraph.dartOfNeighborSet]
            exact fun h => hD.1.2 v w ⟨h, hw⟩
          · rfl
  5. The rotation permutation σ provides a bijection between outgoing darts and incoming darts, so |X| = |Y|.

    We apply Finset.card_bij with the map d ↦ σ d. The rotation system fixes the source vertex of each dart ((σ d).fst = d.fst = v), and the alternating orientation condition states that d is oriented outward if and only if σ d is not. Thus σ maps X into Y. The map is injective because σ is a permutation. It is surjective because for any e ∈ Y, the inverse dart σ⁻¹(e) is rooted at v and satisfies the outward condition by applying the alternating hypothesis to σ⁻¹(e).

    lines 48–71

    uses Finset.card_bij, Equiv.apply_symm_apply

      have h3 : X.card = Y.card := by
        apply Finset.card_bij (fun d (_ : d ∈ X) => σ d)
        · intro d hd
          rw [htest] at hd; rw [htestY]; refine ⟨?_, ?_⟩
          · exact (hσ.1 d).trans hd.1
          · have h := (hD.2 d).mp (hd.1.symm ▸ hd.2)
            rw [hσ.1 d, hd.1] at h
            exact h
        · intro d1 hd1 d2 hd2 heq
          exact σ.injective heq
        · intro e he
          rw [htestY] at he
          refine ⟨σ.symm e, ?_, by simp⟩
          rw [htest]
          have hv : (σ.symm e).fst = v := by
            have h := hσ.1 (σ.symm e)
            simp only [Equiv.apply_symm_apply] at h
            exact h ▸ he.1
          refine ⟨hv, ?_⟩
          have h := (hD.2 (σ.symm e)).mpr
          simp only [Equiv.apply_symm_apply] at h
          rw [← hv]
          apply h
          exact he.1.symm ▸ he.2
  6. The out-degree |T| equals the in-degree |U|.

    Combining the three cardinality equalities gives |T| = |X| = |Y| = |U|, completing the proof that the orientation is Eulerian.

    lines 72–74

      calc T.card = X.card := h1.symm
        _ = Y.card := h3
        _ = U.card := h2
Finset.mem_filter
An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
Finset.mem_univ
Every element of a finite type belongs to Finset.univ.
true_and
True ∧ p simplifies to p.
Finset.card_bij
Two finite sets s and t have equal cardinality if there exists a function between them that maps s into t, is injective on s, and covers every element of t.
SimpleGraph.Dart.ext
Two darts of a simple graph are equal if their underlying directed vertex pairs are equal.
Prod.ext
Two pairs are equal if their first components are equal and their second components are equal.
Or.inl
From a proof of a, deduces a ∨ b.
Or.inr
From a proof of b, deduces a ∨ b.
SimpleGraph.dartOfNeighborSet
Constructs a dart from a vertex v and a proof that w is in the neighbor set of v.
Equiv.apply_symm_apply
Applying an equivalence to the inverse image of x returns x.

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

theorem digraph_is_eulerian_orientation_of_alternating {n : ℕ} (G : SimpleGraph (Fin n))    [DecidableRel G.Adj] (σ : Equiv.Perm G.Dart) (hσ : simple_graph_is_rotation_system G σ)    (D : Digraph (Fin n)) [DecidableRel D.Adj] (hD : digraph_is_alternating_orientation G σ D) :    digraph_is_eulerian_orientation G D := by  classical  unfold digraph_is_eulerian_orientation  refine ⟨hD.1, fun v => ?_⟩  show (Finset.univ.filter (fun w : Fin n => D.Adj v w)).card      = (Finset.univ.filter (fun w : Fin n => D.Adj w v)).card  set T : Finset (Fin n) := Finset.univ.filter (fun w => D.Adj v w) with hT  set U : Finset (Fin n) := Finset.univ.filter (fun w => D.Adj w v) with hU  set X : Finset G.Dart := Finset.univ.filter (fun d => d.fst = v ∧ D.Adj v d.snd) with hX  set Y : Finset G.Dart := Finset.univ.filter (fun d => d.fst = v ∧ ¬ D.Adj v d.snd) with hY  have htest : ∀ d : G.Dart, d ∈ X ↔ d.fst = v ∧ D.Adj v d.snd := by    intro d; rw [hX]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]  have htestY : ∀ d : G.Dart, d ∈ Y ↔ d.fst = v ∧ ¬ D.Adj v d.snd := by    intro d; rw [hY]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]  have h1 : X.card = T.card := by    apply Finset.card_bij (fun d (_ : d ∈ X) => d.snd)    · intro d hd      rw [htest] at hd; rw [hT]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact hd.2    · intro d1 hd1 d2 hd2 heq      rw [htest] at hd1 hd2      exact SimpleGraph.Dart.ext d1 d2 (Prod.ext (hd1.1.trans hd2.1.symm) heq)    · intro w hw      rw [hT] at hw; simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw      refine ⟨G.dartOfNeighborSet v ⟨w, (hD.1.1 v w).mp (Or.inl hw)⟩, ?_, ?_⟩      · rw [htest]; exact ⟨rfl, by simpa [SimpleGraph.dartOfNeighborSet] using hw⟩      · rfl  have h2 : Y.card = U.card := by    apply Finset.card_bij (fun d (_ : d ∈ Y) => d.snd)    · intro d hd      rw [htestY] at hd; rw [hU]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]      have hG : G.Adj v d.snd := hd.1 ▸ d.adj      rcases (hD.1.1 v d.snd).mpr hG with h | h      · exact absurd h hd.2      · exact h    · intro d1 hd1 d2 hd2 heq      rw [htestY] at hd1 hd2      exact SimpleGraph.Dart.ext d1 d2 (Prod.ext (hd1.1.trans hd2.1.symm) heq)    · intro w hw      rw [hU] at hw; simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw      refine ⟨G.dartOfNeighborSet v ⟨w, (hD.1.1 v w).mp (Or.inr hw)⟩, ?_, ?_⟩      · rw [htestY]; refine ⟨rfl, ?_⟩        simp only [SimpleGraph.dartOfNeighborSet]        exact fun h => hD.1.2 v w ⟨h, hw⟩      · rfl  have h3 : X.card = Y.card := by    apply Finset.card_bij (fun d (_ : d ∈ X) => σ d)    · intro d hd      rw [htest] at hd; rw [htestY]; refine ⟨?_, ?_⟩      · exact (hσ.1 d).trans hd.1      · have h := (hD.2 d).mp (hd.1.symm ▸ hd.2)        rw [hσ.1 d, hd.1] at h        exact h    · intro d1 hd1 d2 hd2 heq      exact σ.injective heq    · intro e he      rw [htestY] at he      refine ⟨σ.symm e, ?_, by simp⟩      rw [htest]      have hv : (σ.symm e).fst = v := by        have h := hσ.1 (σ.symm e)        simp only [Equiv.apply_symm_apply] at h        exact h ▸ he.1      refine ⟨hv, ?_⟩      have h := (hD.2 (σ.symm e)).mpr      simp only [Equiv.apply_symm_apply] at h      rw [← hv]      apply h      exact he.1.symm ▸ he.2  calc T.card = X.card := h1.symm    _ = Y.card := h3    _ = U.card := h2
See it in the graphDiscuss this resultChallenge it