digraph_is_eulerian_orientation_of_alternating
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|.
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.
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
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.
uses
Finset.mem_filter,Finset.mem_univ,true_andset 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]
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.
uses
Finset.card_bij,Finset.mem_filter,Finset.mem_univ,true_and,SimpleGraph.Dart.ext,Prod.ext,Or.inl,SimpleGraph.dartOfNeighborSethave 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
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).
uses
Finset.card_bij,Finset.mem_filter,Finset.mem_univ,true_and,SimpleGraph.Dart.ext,Prod.ext,Or.inr,SimpleGraph.dartOfNeighborSethave 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
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).
uses
Finset.card_bij,Equiv.apply_symm_applyhave 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
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.
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.
- In Lean, darts are formal pairs (source, target) bundled with an adjacency proof; transitioning between vertices and darts requires explicit constructors like `SimpleGraph.dartOfNeighborSet` and extensionality lemmas.
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.
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