AFTD Auto-Formalizing Theoretical Domains

digraph_invert_is_tournament

theoremverified

Inverting a vertex set of a tournament gives a tournament.

Statement

theorem digraph_invert_is_tournament {V : Type*} (D : Digraph V) (X : Set V)
    (hD : digraph_is_tournament D) : digraph_is_tournament (digraph_invert D X)
Source
Sanity lemma for digraph_invert and digraph_is_tournament (arXiv:2610.13798, Sec. 1).
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • digraph_invertThe inversion of a vertex set X in a digraph D: the digraph obtained by reversing every arc with both endpoints in X and keeping every…
  • 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

To show that inverting the edges within a vertex subset $X$ of a tournament $D$ yields another tournament, we check the two defining tournament properties: irreflexivity and the existence of exactly one directed edge between distinct vertices. Irreflexivity is preserved because any self-loop in the inverted graph would imply a self-loop in $D$. For any distinct vertices $x$ and $y$, we perform a case analysis on their membership in $X$: if both lie in $X$, the directed edge between them is reversed, and if at least one lies outside $X$, it remains unchanged, so in all cases exactly one directed edge connects them.

  1. To show that the inverted graph is a tournament, it suffices to prove that it has no self-loops and that between any two distinct vertices, exactly one directed edge exists.

    We unpack the hypothesis that $D$ is a tournament into two properties: irreflexivity (no vertex has a self-loop) and the tournament condition (any two distinct vertices have an edge in exactly one direction). We then reduce the goal to verifying these same two conditions for the inverted graph.

    lines 3–4

      obtain ⟨h1, h2⟩ := hD
      refine ⟨fun x => ?_, fun x y hxy => ?_⟩
  2. The inverted graph has no self-loops.

    Unfolding the definition of edge inversion, a self-loop at $x$ would require a self-loop at $x$ in $D$, regardless of whether $x \in X$. Since $D$ is a tournament, it has no self-loops, so neither branch can hold.

    line 5

      · simp only [digraph_invert]; have := h1 x; tauto
  3. Between any two distinct vertices, exactly one directed edge exists in the inverted graph.

    Unfolding the definition of edge inversion, we instantiate the tournament condition for $D$ on both $(x, y)$ and $(y, x)$, using `Ne.symm` to deduce $y \neq x$ from $x \neq y$. We then split into four cases based on whether $x \in X$ and $y \in X$. If both vertices are in $X$, the edge between them is reversed; otherwise, the edge is unchanged. In each case, exactly one directed edge exists between $x$ and $y$ because that was true in $D$.

    lines 6–8

    uses Ne.symm

      · simp only [digraph_invert]
        have := h2 x y hxy; have := h2 y x (Ne.symm hxy)
        by_cases hx : x ∈ X <;> by_cases hy : y ∈ X <;> simp [hx, hy] <;> tauto
Ne.symm
If $a \neq b$, then $b \neq a$.

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

theorem digraph_invert_is_tournament {V : Type*} (D : Digraph V) (X : Set V)    (hD : digraph_is_tournament D) : digraph_is_tournament (digraph_invert D X) := by  obtain ⟨h1, h2⟩ := hD  refine ⟨fun x => ?_, fun x y hxy => ?_⟩  · simp only [digraph_invert]; have := h1 x; tauto  · simp only [digraph_invert]    have := h2 x y hxy; have := h2 y x (Ne.symm hxy)    by_cases hx : x ∈ X <;> by_cases hy : y ∈ X <;> simp [hx, hy] <;> tauto
See it in the graphDiscuss this resultChallenge it