AFTD Auto-Formalizing Theoretical Domains

digraph_ext_iff

theoremverified

Two digraphs on the same vertex type are equal if and only if their adjacency relations are logically equivalent.

Statement

theorem digraph_ext_iff {V : Type*} (D₁ D₂ : Digraph V) :
    D₁ = D₂ ↔ ∀ u v, D₁.Adj u v ↔ D₂.Adj u v
Source
step towards three_connected_plane_eulerian_arborescence_minimizers_alternating
Verified
28 Oct 2026
Axioms
Quot.soundpropext
Used by 1

The proof, explained

Two digraphs on the same vertex type are equal if and only if their adjacency relations are logically equivalent. The forward direction is immediate by substituting equals for equals. The converse holds because a digraph is defined solely by its adjacency relation, so equality of digraphs reduces to equality of relations, which follows from pointwise equivalence via function extensionality and propositional extensionality.

  1. The forward implication holds: if two digraphs are equal, their adjacency relations are equivalent for all pairs of vertices.

    The equivalence is split into two implications. Assuming $D₁ = D₂$, we substitute $D₁$ for $D₂$. The goal then becomes $D₁.\text{Adj } u\ v \leftrightarrow D₁.\text{Adj } u\ v$ for all $u, v$, which holds trivially by reflexivity.

    lines 4–7

      constructor
      · intro h
        subst h
        simp
  2. For the reverse implication, proving $D₁ = D₂$ reduces to showing that their underlying adjacency relations are equal as functions.

    We assume that $D₁$ and $D₂$ have logically equivalent adjacency relations on all vertex pairs. Decomposing both digraphs into their constructor records via `cases`, equality of the two digraphs simplifies via constructor injectivity (`Digraph.mk.injEq`) to equality of their underlying adjacency relations.

    lines 8–11

    uses Digraph.mk.injEq

      · intro h
        cases D₁
        cases D₂
        simp only [Digraph.mk.injEq]
  3. The adjacency relations are equal, which proves $D₁ = D₂$.

    By function extensionality (`funext`), two relations are equal if they agree on all pairs of arguments $u, v$. For arbitrary vertices $u$ and $v$, the hypothesis provides the equivalence $D₁.\text{Adj } u\ v \leftrightarrow D₂.\text{Adj } u\ v$. Propositional extensionality (`propext`) turns this equivalence into equality of truth values, concluding the proof.

    lines 12–13

    uses propext

        funext u v
        exact propext (h u v)
Digraph.mk.injEq
Two digraphs constructed from adjacency relations are equal if and only if their adjacency relations are equal.
propext
Propositional extensionality: two propositions are equal if and only if they are logically equivalent.

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

/-- Two digraphs on the same vertex type are equal if and only if their adjacency relations are logically equivalent. -/theorem digraph_ext_iff {V : Type*} (D₁ D₂ : Digraph V) :    D₁ = D₂ ↔ ∀ u v, D₁.Adj u v ↔ D₂.Adj u v := by  constructor  · intro h    subst h    simp  · intro h    cases D₁    cases D₂    simp only [Digraph.mk.injEq]    funext u v    exact propext (h u v)
See it in the graphDiscuss this resultChallenge it