digraph_invert_is_tournament
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
- tournament_exists_decycling_familyEvery finite tournament can be made acyclic by finitely many inversions (so its inversion number is attained).
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.
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.
obtain ⟨h1, h2⟩ := hD refine ⟨fun x => ?_, fun x y hxy => ?_⟩
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.
· simp only [digraph_invert]; have := h1 x; tauto
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$.
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$.
- The case analysis across the four membership combinations for $x, y \in X$ and the resulting propositional simplifications are handled by `simp` and `tauto`.
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.
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