digraph_eulerian_orientation_reversal
theoremverified
The reversal of an Eulerian orientation of a simple graph is also an Eulerian orientation.
Statement
theorem digraph_eulerian_orientation_reversal {n : ℕ} (G : SimpleGraph (Fin n)) (D : Digraph (Fin n)) [DecidableRel D.Adj] (hD : digraph_is_eulerian_orientation G D) : @digraph_is_eulerian_orientation n G ⟨fun u v => D.Adj v u⟩ (fun u v => inferInstanceAs (Decidable (D.Adj v u)))
- Source
- step towards three_connected_plane_eulerian_arborescence_minimizers_alternating
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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:…
- 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…
Lean source view module on GitHub
/-- The reversal of an Eulerian orientation of a simple graph is also an Eulerian orientation. -/ theorem digraph_eulerian_orientation_reversal {n : ℕ} (G : SimpleGraph (Fin n)) (D : Digraph (Fin n)) [DecidableRel D.Adj] (hD : digraph_is_eulerian_orientation G D) : @digraph_is_eulerian_orientation n G ⟨fun u v => D.Adj v u⟩ (fun u v => inferInstanceAs (Decidable (D.Adj v u))) := by unfold digraph_is_eulerian_orientation at * rcases hD with ⟨⟨h1, h2⟩, hD_deg⟩ constructor · constructor · intro u v rw [or_comm] exact h1 u v · intro u v rw [and_comm] exact h2 u v · intro v exact (hD_deg v).symm