digraph_reverse_reverse
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
- digraph_is_quasi_kernel_empty_of_isEmptyIn an empty digraph, the empty set is a quasi-kernel.
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.
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.
cases DThe 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.
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
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.
/-- 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