digraph_ext_iff
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
- digraph_alternating_orientation_unique_up_to_reversalOn any connected graph with a rotation system σ, an alternating orientation is uniquely determined up to reversal: any two alternating…
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.
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.
constructor · intro h subst h simp
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.
uses
Digraph.mk.injEq· intro h cases D₁ cases D₂ simp only [Digraph.mk.injEq]
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.
uses
propextfunext 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.
- In Lean, a digraph is formalized as a structure wrapping its adjacency relation, so proving digraph equality requires unpacking constructors (`Digraph.mk.injEq`) and applying propositional extensionality (`propext`), steps that are implicit on paper.
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.
/-- 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)