digraph_reverse_is_tournament
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
- tournament_inversion_number_reverseFor a finite tournament D: inv(D̄) = inv(D), where D̄ is D with every arc reversed.
- tournament_dijoin_reverse_inversion_number_le_of_eq_maxWhenever inv(D₁ → D₂) attains its theoretical minimum max(inv(D₁), inv(D₂)), the inequality inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂) holds.
- tournament_dijoin_swap_inversion_number_eq_reverseFor finite tournaments D₁, D₂: inv(D₂ → D₁) = inv(D̄₁ → D̄₂). So the symmetry conjecture inv(D₁ → D₂) = inv(D₂ → D₁) says exactly that the…
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).
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).
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)⟩