AFTD Auto-Formalizing Theoretical Domains

digraph_reverse_reverse

theoremverified

Reversing a digraph twice yields the original digraph.

Statement

theorem digraph_reverse_reverse {V : Type*} (D : Digraph V) :
    digraph_reverse (digraph_reverse D) = D
Source
step towards tournament_dijoin_inversion_number_symm
Verified
21 Oct 2026
Axioms
none — Lean reports it depends on no axioms
Built on 1
  • digraph_reverseThe reverse D̄ of a digraph D: the digraph on the same vertices with every arc turned around.
Used by 1

The proof, explained

A directed graph is determined entirely by its binary adjacency relation, and reversing the digraph corresponds to transposing this relation. By unpacking $D$ into its underlying adjacency relation, reversing twice transposes the relation twice, which restores the original relation by definition. The theorem then holds by definitional equality.

  1. It suffices to verify the equality when $D$ is given explicitly by its adjacency relation.

    We decompose the digraph $D$ into its structure constructor $\langle \text{Adj} \rangle$, where $\text{Adj} : V \to V \to \text{Prop}$ is its adjacency relation.

    line 4

      cases D
  2. The reverse of the reverse of $D$ is definitionally equal to $D$.

    By definition of `digraph_reverse`, reversing a digraph swaps the arguments of its adjacency relation, sending $(x, y)$ to $(y, x)$. Applying this operation twice yields $\text{Adj}(x, y)$ again, so the double reverse is definitionally identical to the original digraph, which reflexivity (`rfl`) confirms.

    line 5

      rfl

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

/-- The reverse of the reverse of a digraph is the original digraph. -/theorem digraph_reverse_reverse {V : Type*} (D : Digraph V) :    digraph_reverse (digraph_reverse D) = D := by  cases D  rfl
See it in the graphDiscuss this resultChallenge it