tournament_reverse_arc_is_tournament
If T is a tournament with an arc u → v, reversing that arc gives another tournament.
Statement
theorem tournament_reverse_arc_is_tournament {n : ℕ} (T : Digraph (Fin n)) [DecidableRel T.Adj]
(hT : digraph_is_tournament T) (u v : Fin n) (huv : T.Adj u v) :
digraph_is_tournament (digraph_reverse_arc T u v)- Source
- step towards tournament_not_near_regular_exists_improving_tournament
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- digraph_reverse_arc_adjReversing the arc between u and v: the pair (u,v) gets the adjacency that (v,u) had, and any other pair keeps its adjacency.
- 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 1
- tournament_four_not_near_regular_exists_improvingThe m = 2 case of the target, settled by finite computation: a non-near-regular tournament on 4 vertices has at most 9 arborescences while…
The proof, explained
Reversing an arc u → v in a tournament T modifies the edge relation only between the vertices u and v. Since T is irreflexive, u ≠ v, which ensures that no self-loops are created at any vertex. For any distinct pair of vertices, if the pair is {u, v}, the unique existing arc is simply inverted, and if the pair is not {u, v}, the arcs between them are untouched, preserving the tournament property in both cases.
The vertices u and v are distinct (u ≠ v).
If u = v, the assumed arc u → v would be a self-loop u → u in T. But T is a tournament, hence irreflexive (hT.1), which is a contradiction.
have unev : u ≠ v := by rintro rfl exact hT.1 u huv
To show the modified graph is a tournament, it suffices to prove it has no self-loops and that every pair of distinct vertices has exactly one directed edge.
By definition (`digraph_is_tournament`), a tournament is an irreflexive directed graph where every pair of distinct vertices has an arc in exactly one direction. The `constructor` tactic splits the goal into these two independent obligations.
constructorThe reversed graph has no self-loops: for all x, ¬(digraph_reverse_arc T u v).Adj x x.
Unfolding the definition of `digraph_reverse_arc`, an edge from x to x is affected only if (x = u ∧ x = v) or (x = v ∧ x = u). Either condition forces u = v by transitivity of equality, contradicting u ≠ v. In the remaining case, the edge relation is unchanged from T, where self-loops are ruled out by the irreflexivity of T (hT.1).
· intro x dsimp [digraph_reverse_arc] split_ifs with h · cases h with | inl h1 => exact (unev (h1.1.symm.trans h1.2)).elim | inr h2 => exact (unev (h2.2.symm.trans h2.1)).elim · exact hT.1 x
For distinct vertices x and y, the condition that the ordered pair (x, y) equals (u, v) or (v, u) is logically equivalent to the condition that (y, x) equals (u, v) or (v, u).
The reversal condition tests whether the unordered pair {x, y} matches {u, v}. Since this property is symmetric in x and y, propositional reasoning (`tauto`) establishes that the condition holds for (x, y) if and only if it holds for (y, x).
· intro x y hne dsimp [digraph_reverse_arc] have hiff : ((x = u ∧ y = v) ∨ (x = v ∧ y = u)) ↔ ((y = u ∧ x = v) ∨ (y = v ∧ x = u)) := by tauto
If {x, y} = {u, v}, exactly one directed arc exists between x and y in the reversed graph.
When the pair is {u, v}, the reversal condition holds for both (x, y) and (y, x). By `if_pos`, the adjacency between x and y in the new graph is that between y and x in T, and vice versa. Since y ≠ x and T is a tournament, exactly one of the two orientations held in T (hT.2), so exactly one holds in the reversed graph.
uses
if_posby_cases h : (x = u ∧ y = v) ∨ (x = v ∧ y = u) · have h' : (y = u ∧ x = v) ∨ (y = v ∧ x = u) := hiff.mp h rw [if_pos h, if_pos h'] exact hT.2 y x hne.symm
If {x, y} ≠ {u, v}, exactly one directed arc exists between x and y in the reversed graph.
When the pair is not {u, v}, the reversal condition is false for both (x, y) and (y, x). By `if_neg`, the adjacencies between x and y in the new graph are identical to those in T. Since T is a tournament, the tournament condition (hT.2) transfers directly.
uses
if_neg· have h' : ¬ ((y = u ∧ x = v) ∨ (y = v ∧ x = u)) := by rwa [← hiff] rw [if_neg h, if_neg h'] exact hT.2 x y hne
if_pos- If a condition c is true, then `if c then t else e` simplifies to t.
if_neg- If a condition c is false, then `if c then t else e` simplifies to e.
- In lines 13 and 14, the impossible cases where u = v are eliminated using Lean's dot-notation `.elim` on a proof of `False` (which invokes the library principle `False.elim`).
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.
/-- Reversing the arc u → v of a tournament again yields a tournament. -/theorem tournament_reverse_arc_is_tournament {n : ℕ} (T : Digraph (Fin n)) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (u v : Fin n) (huv : T.Adj u v) : digraph_is_tournament (digraph_reverse_arc T u v) := by have unev : u ≠ v := by rintro rfl exact hT.1 u huv constructor · intro x dsimp [digraph_reverse_arc] split_ifs with h · cases h with | inl h1 => exact (unev (h1.1.symm.trans h1.2)).elim | inr h2 => exact (unev (h2.2.symm.trans h2.1)).elim · exact hT.1 x · intro x y hne dsimp [digraph_reverse_arc] have hiff : ((x = u ∧ y = v) ∨ (x = v ∧ y = u)) ↔ ((y = u ∧ x = v) ∨ (y = v ∧ x = u)) := by tauto by_cases h : (x = u ∧ y = v) ∨ (x = v ∧ y = u) · have h' : (y = u ∧ x = v) ∨ (y = v ∧ x = u) := hiff.mp h rw [if_pos h, if_pos h'] exact hT.2 y x hne.symm · have h' : ¬ ((y = u ∧ x = v) ∨ (y = v ∧ x = u)) := by rwa [← hiff] rw [if_neg h, if_neg h'] exact hT.2 x y hne