digraph_reverse_arc_adj
Reversing the arc between u and v: the pair (u,v) gets the adjacency that (v,u) had, and any other pair keeps its adjacency.
Statement
theorem digraph_reverse_arc_adj {n : ℕ} (D : Digraph (Fin n)) (u v : Fin n) :
(∀ x y : Fin n, ¬ (x = u ∧ y = v) → ¬ (x = v ∧ y = u) →
((digraph_reverse_arc D u v).Adj x y ↔ D.Adj x y)) ∧
((digraph_reverse_arc D u v).Adj u v ↔ D.Adj v u) ∧
((digraph_reverse_arc D u v).Adj v u ↔ D.Adj u v)- Source
- step towards tournament_not_near_regular_exists_improving_tournament
- Verified
- 31 Oct 2026
- Axioms
propext- Built on 1
- digraph_reverse_arcThe digraph obtained from D by reversing the arc between u and v: the two vertices exchange which of them points to the other, and every…
- Used by 2
- tournament_reverse_arc_is_tournamentIf T is a tournament with an arc u → v, reversing that arc gives another tournament.
- digraph_arborescence_count_at_reverse_arc_add_throughFor a tournament with an arc u → v and any root r, the number of arborescences towards r grows by exactly (through-count of v → u after…
The proof, explained
The theorem states that reversing the arc between $u$ and $v$ swaps their mutual adjacency while leaving all other pairs unchanged. By definition, `digraph_reverse_arc` is an if-then-else condition checking whether the query pair is $(u, v)$ or $(v, u)$. The proof splits the conjunction into three goals and simplifies each using this definition: hypotheses $h_1$ and $h_2$ route non-target pairs to the unchanged branch, while the target pairs $(u, v)$ and $(v, u)$ satisfy the condition by reflexivity of equality and evaluate to the swapped adjacency.
The proof reduces to three subgoals: verifying the adjacency for unrelated vertex pairs, for $(u, v)$, and for $(v, u)$.
We split the three-part conjunction into its components. For the first component, we introduce arbitrary vertices $x$ and $y$, along with the hypotheses $h_1 : \neg (x = u \land y = v)$ and $h_2 : \neg (x = v \land y = u)$ asserting that the pair is neither $(u, v)$ nor $(v, u)$.
refine ⟨fun x y h1 h2 => ?_, ?_, ?_⟩
Any pair $(x, y)$ distinct from $(u, v)$ and $(v, u)$ retains its original adjacency from $D$. automation
By definition, `digraph_reverse_arc` checks whether $(x = u \land y = v) \lor (x = v \land y = u)$. Both conditions are false by hypotheses $h_1$ and $h_2$, so the condition evaluates to the default branch $D.\text{Adj}(x, y)$. The resulting equivalence $D.\text{Adj}(x, y) \leftrightarrow D.\text{Adj}(x, y)$ is trivially true.
· simp [h1, h2]An arc from $u$ to $v$ exists in the modified digraph if and only if $D$ has an arc from $v$ to $u$. automation
Specializing to the pair $(u, v)$, the condition $(u = u \land v = v) \lor (u = v \land v = u)$ holds because $u = u$ and $v = v$. The definition therefore selects the reversed adjacency $D.\text{Adj}(v, u)$, leaving the reflexive equivalence $D.\text{Adj}(v, u) \leftrightarrow D.\text{Adj}(v, u)$, which simplifies to true.
· simpAn arc from $v$ to $u$ exists in the modified digraph if and only if $D$ has an arc from $u$ to $v$. automation
Similarly, for the pair $(v, u)$, the condition holds because $v = v$ and $u = u$. The definition evaluates to $D.\text{Adj}(u, v)$, leaving the reflexive equivalence $D.\text{Adj}(u, v) \leftrightarrow D.\text{Adj}(u, v)$, which simplifies to true.
· simp
- The tactic `simp` automatically unfolds the definition of `digraph_reverse_arc`, which is defined via an if-then-else case split on whether the ordered pair of vertices is $(u, v)$ or $(v, u)$.
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.
/-- Adjacency of the single-arc reversal: reversed on the pair {u,v}, unchanged elsewhere. -/theorem digraph_reverse_arc_adj {n : ℕ} (D : Digraph (Fin n)) (u v : Fin n) : (∀ x y : Fin n, ¬ (x = u ∧ y = v) → ¬ (x = v ∧ y = u) → ((digraph_reverse_arc D u v).Adj x y ↔ D.Adj x y)) ∧ ((digraph_reverse_arc D u v).Adj u v ↔ D.Adj v u) ∧ ((digraph_reverse_arc D u v).Adj v u ↔ D.Adj u v) := by refine ⟨fun x y h1 h2 => ?_, ?_, ?_⟩ · simp [h1, h2] · simp · simp