AFTD Auto-Formalizing Theoretical Domains

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