AFTD Auto-Formalizing Theoretical Domains

digraph_reverse_arc_adj

theoremverified

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

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.

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

    line 7

      refine ⟨fun x y h1 h2 => ?_, ?_, ?_⟩
  2. 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.

    line 8

      · simp [h1, h2]
  3. 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.

    line 9

      · simp
  4. An 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.

    line 10

      · simp

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

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