AFTD Auto-Formalizing Theoretical Domains

digraph_flip_by_matrix_zero

theoremverified

Flipping by the zero matrix changes nothing.

Statement

theorem digraph_flip_by_matrix_zero {V : Type*} (D : Digraph V) :
    digraph_flip_by_matrix D 0 = D
Source
Sanity lemma for digraph_flip_by_matrix (arXiv:2610.13798, Sec. 2.2).
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • digraph_flip_by_matrixGiven a digraph D and a (symmetric) matrix M over F₂ indexed by its vertices, the digraph obtained by reversing every arc uv with M_uv = 1…
Used by 1

The proof, explained

The proof establishes that flipping a directed graph D by the zero matrix returns D by checking equality on all edges. Unfolding the definition of `digraph_flip_by_matrix` with matrix 0, every matrix entry is 0 ≠ 1 in ℤ/2ℤ, so no edges are reversed and the adjacency relation is unchanged.

  1. To prove the two directed graphs are equal, it suffices to show they have identical adjacency relations on all pairs of vertices x and y.

    By extensionality for directed graphs (`ext x y`), two graphs are equal if and only if for every pair of vertices x, y ∈ V, there is an edge from x to y in the first graph if and only if there is an edge from x to y in the second graph.

    line 3

      ext x y
  2. For any vertices x and y, the flipped graph has an edge from x to y if and only if the original graph D has an edge from x to y.

    Unfolding the definition of `digraph_flip_by_matrix`, the adjacency condition for the zero matrix is (0 x y = 1 ∧ D.Adj y x) ∨ (0 x y ≠ 1 ∧ D.Adj x y). In ℤ/2ℤ, the entry 0 is not equal to 1, making the first clause false and the second clause equivalent to D.Adj x y; the simplifier discharges the equivalence.

    line 4

    uses digraph_flip_by_matrix

      simp [digraph_flip_by_matrix]
digraph_flip_by_matrix
The operation that modifies a directed graph according to a matrix over ℤ/2ℤ, keeping the edge direction (x → y) where the matrix entry is 0 and reversing it (to y → x) where the entry is 1.

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_flip_by_matrix_zero {V : Type*} (D : Digraph V) :    digraph_flip_by_matrix D 0 = D := by  ext x y  simp [digraph_flip_by_matrix]
See it in the graphDiscuss this resultChallenge it