digraph_invert_invert
Inverting the same vertex set twice gives back the digraph.
Statement
theorem digraph_invert_invert {V : Type*} (D : Digraph V) (X : Set V) : digraph_invert (digraph_invert D X) X = D
- Source
- Sanity lemma for digraph_invert (arXiv:2610.13798, Sec. 1).
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_invertThe inversion of a vertex set X in a digraph D: the digraph obtained by reversing every arc with both endpoints in X and keeping every…
The proof, explained
By extensionality, two digraphs are identical if they share the same adjacency relation on all pairs of vertices. Digraph inversion with respect to a vertex set X reverses edges between vertices that both lie in X and preserves all other edges. A four-way case analysis on whether the endpoints belong to X confirms that inverting twice either reverses an edge twice or preserves it twice, recovering the original digraph D in every case.
To show that the doubly-inverted digraph equals D, it suffices to show that they have the same directed edges between any two vertices x and y.
Two directed graphs are equal if and only if their vertex sets and adjacency relations coincide. Applying extensionality reduces the equality of digraphs to an equivalence of adjacency relations for arbitrary vertices x and y.
ext x yThe adjacency condition in the doubly-inverted digraph is expanded explicitly in terms of vertex membership in X and the edges of D.
Unfolding the definition of digraph inversion twice expresses adjacency in the doubly-inverted digraph as a Boolean condition: an edge is reversed when both endpoints lie in X, and left unchanged otherwise.
uses
digraph_invertsimp only [digraph_invert]For all vertices x and y, the edge condition in the doubly-inverted digraph is equivalent to D.Adj x y.
We split into four cases based on whether x ∈ X and whether y ∈ X. When both x ∈ X and y ∈ X, the edge orientation is reversed twice, restoring D.Adj x y. In the other three cases where at least one vertex is not in X, the edge orientation is left unchanged in both inversion steps, which likewise simplifies to D.Adj x y.
by_cases hx : x ∈ X <;> by_cases hy : y ∈ X <;> simp [hx, hy]
digraph_invert- The digraph obtained from a digraph D by reversing edges between pairs of vertices that both belong to X, while leaving all other edges unchanged.
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_invert_invert {V : Type*} (D : Digraph V) (X : Set V) : digraph_invert (digraph_invert D X) X = D := by ext x y simp only [digraph_invert] by_cases hx : x ∈ X <;> by_cases hy : y ∈ X <;> simp [hx, hy]