digraph_dijoin_is_tournament
The dijoin of two tournaments is a tournament.
Statement
theorem digraph_dijoin_is_tournament {V W : Type*} (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) : digraph_is_tournament (digraph_dijoin D₁ D₂)
- Source
- Sanity lemma for digraph_dijoin (arXiv:2610.13798, Sec. 1).
- Verified
- 13 Oct 2026
- Axioms
propext- Built on 2
- digraph_dijoinThe dijoin D₁ → D₂: disjoint copies of D₁ and D₂ together with every arc from a vertex of D₁ to a vertex of D₂.
- 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 5
- tournament_dijoin_inversion_number_symm_of_is_acyclic_leftThe symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₁ is acyclic (a transitive tournament): both sides equal inv(D₂).
- tournament_dijoin_inversion_number_le_symm_add_twoFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≤ inv(D₂ → D₁) + 2 (with D₁, D₂ swapped this gives |inv(D₁ → D₂) − inv(D₂ → D₁)| ≤ 2): invert…
- tournament_min_rank_le_dijoinFor finite tournaments D₁, D₂: tmr(D₁ → D₂) ≥ max(tmr(D₁), tmr(D₂)) (hence ≥ (tmr(D₁) + tmr(D₂))/2), because the principal submatrix of a…
- 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…
- tournament_inversion_number_le_dijoinFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≥ max(inv(D₁), inv(D₂)), since D₁ and D₂ are induced subtournaments of the dijoin and a…
The proof, explained
To show that the dijoin of two tournaments $D_1$ and $D_2$ is a tournament, we verify the two defining conditions: absence of self-loops and the existence of a unique directed edge between every pair of distinct vertices. Looplessness holds because any vertex belongs to either $D_1$ or $D_2$, both of which are tournaments and therefore loopless. For distinct vertices, if both belong to the same constituent tournament, its tournament property applies directly. If they belong to different tournaments, all edges in the dijoin point from the first tournament to the second and none point back, which satisfies the condition.
To show that the dijoin is a tournament, it suffices to prove that it has no self-loops and that every pair of distinct vertices has exactly one directed edge between them.
By definition, a directed graph is a tournament if no vertex has a self-loop and for every pair of distinct vertices $x \ne y$, there is an edge from $x$ to $y$ if and only if there is no edge from $y$ to $x$. The goal is decomposed into these two independent conditions.
refine ⟨fun x => ?_, fun x y hxy => ?_⟩
The dijoin has no self-loops.
Any vertex $x$ in the disjoint union $V \oplus W$ comes from either $V$ or $W$. In the first case ($x = \operatorname{inl} a$), a self-loop would be an edge from $a$ to $a$ in $D_1$, which cannot exist since $D_1$ is a tournament ($h_1$). In the second case ($x = \operatorname{inr} a$), a self-loop would be an edge in $D_2$, which cannot exist since $D_2$ is a tournament ($h_2$).
· rcases x with a | a · exact h₁.1 a · exact h₂.1 a
For any two distinct vertices $x \ne y$ in the dijoin, there is an edge from $x$ to $y$ if and only if there is no edge from $y$ to $x$.
We consider four cases based on which constituent tournament contains each vertex: - If both vertices belong to $V$ ($x = \operatorname{inl} a, y = \operatorname{inl} b$), then $a \ne b$ because $x \ne y$; the equivalence then follows from the tournament property of $D_1$ ($h_1$). - If $x \in V$ and $y \in W$ ($x = \operatorname{inl} a, y = \operatorname{inr} b$), by definition of the dijoin the forward edge is present and the reverse edge is absent; the equivalence reduces to $\text{True} \leftrightarrow \neg\text{False}$, which holds. - If $x \in W$ and $y \in V$ ($x = \operatorname{inr} a, y = \operatorname{inl} b$), symmetrically the forward edge is absent and the reverse edge is present, reducing to $\text{False} \leftrightarrow \neg\text{True}$. - If both vertices belong to $W$ ($x = \operatorname{inr} a, y = \operatorname{inr} b$), then $a \ne b$, and the equivalence follows from the tournament property of $D_2$ ($h_2$).
· rcases x with a | a <;> rcases y with b | b · exact h₁.2 a b (fun h => hxy (by rw [h])) · simp [digraph_dijoin] · simp [digraph_dijoin] · exact h₂.2 a b (fun h => hxy (by rw [h]))
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_dijoin_is_tournament {V W : Type*} (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) : digraph_is_tournament (digraph_dijoin D₁ D₂) := by refine ⟨fun x => ?_, fun x y hxy => ?_⟩ · rcases x with a | a · exact h₁.1 a · exact h₂.1 a · rcases x with a | a <;> rcases y with b | b · exact h₁.2 a b (fun h => hxy (by rw [h])) · simp [digraph_dijoin] · simp [digraph_dijoin] · exact h₂.2 a b (fun h => hxy (by rw [h]))