AFTD Auto-Formalizing Theoretical Domains

digraph_reverse_is_tournament

theoremverified

The reverse of a tournament is a tournament.

Statement

theorem digraph_reverse_is_tournament {V : Type*} (D : Digraph V)
    (h : digraph_is_tournament D) : digraph_is_tournament (digraph_reverse D)
Source
Sanity lemma for digraph_reverse (arXiv:2610.13798, Sec. 4).
Verified
13 Oct 2026
Axioms
none — Lean reports it depends on no axioms
Built on 2
  • digraph_reverseThe reverse D̄ of a digraph D: the digraph on the same vertices with every arc turned around.
  • digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
Used by 3

The proof, explained

To prove that the reversal of a tournament D is itself a tournament, we verify its two defining conditions: looplessness and the tournament edge condition between distinct vertices. Both hold directly by unpacking the definition of the reversed graph: a self-loop in the reverse is a self-loop in D, and the condition for an edge between distinct x and y in the reverse is the tournament condition of D applied to the pair (y, x).

  1. The reversal of D is loopless and has exactly one directed edge between any pair of distinct vertices.

    By definition, a tournament requires two properties. First, it has no self-loops: for any vertex x, the reversed graph has no loop at x if and only if ¬ D.Adj x x, which is provided directly by the loopless property of D (h.1 x). Second, for any two vertices x and y with x ≠ y, there must be an edge from x to y in the reversed graph if and only if there is not an edge from y to x; by definition of digraph_reverse, this unfolds to D.Adj y x ↔ ¬ D.Adj x y. Since x ≠ y implies y ≠ x by Ne.symm, this equivalence is precisely the tournament condition of D applied to the pair (y, x) (h.2 y x).

    line 3

    uses Ne.symm

      ⟨fun x => h.1 x, fun x y hxy => h.2 y x (Ne.symm hxy)⟩
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem digraph_reverse_is_tournament {V : Type*} (D : Digraph V)    (h : digraph_is_tournament D) : digraph_is_tournament (digraph_reverse D) :=  ⟨fun x => h.1 x, fun x y hxy => h.2 y x (Ne.symm hxy)⟩
See it in the graphDiscuss this resultChallenge it