AFTD Auto-Formalizing Theoretical Domains

tournament_reverse_arc_is_tournament

theoremverified

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

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.

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

    lines 5–7

      have unev : u ≠ v := by
        rintro rfl
        exact hT.1 u huv
  2. 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.

    line 8

      constructor
  3. The 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).

    lines 9–15

      · 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
  4. 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).

    lines 16–19

      · 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
  5. 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.

    lines 20–23

    uses if_pos

        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
  6. 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.

    lines 24–26

    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.

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

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