AFTD Auto-Formalizing Theoretical Domains

digraph_invert_invert

theoremverified

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.

  1. 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.

    line 3

      ext x y
  2. The 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.

    line 4

    uses digraph_invert

      simp only [digraph_invert]
  3. 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.

    line 5

      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

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