digraph_is_acyclic_dijoin
The dijoin of two acyclic digraphs is acyclic: a directed walk never comes back from the D₂ side to the D₁ side.
Statement
theorem digraph_is_acyclic_dijoin {V W : Type*} (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_acyclic D₁) (h₂ : digraph_is_acyclic D₂) : digraph_is_acyclic (digraph_dijoin D₁ D₂)
- Source
- Helper for the upper bound inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂) of arXiv:2610.13798, Sec. 1.
- Verified
- 13 Oct 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 2
- digraph_is_acyclicA digraph is acyclic when it has no directed cycle: no vertex reaches itself by a nonempty directed walk. For a tournament this means it…
- 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₂.
- Used by 1
- tournament_dijoin_inversion_number_le_addFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂), by inverting an optimal family of D₁ and then one of D₂.
The proof, explained
The proof proceeds by establishing a key lemma about directed walks in the dijoin: any walk between vertices in D₁ stays within D₁, any walk between vertices in D₂ stays within D₂, and no walk ever moves from D₂ back to D₁. This is proved by induction on the length of the walk (the transitive closure of the adjacency relation), using the fact that edges in the dijoin only stay within each component or go forward from D₁ to D₂. Finally, any cycle in the dijoin would have to be contained entirely within D₁ or entirely within D₂, contradicting the assumed acyclicity of D₁ or D₂.
For any single edge in the dijoin, an edge between vertices in D₁ is an edge of D₁, an edge between vertices in D₂ is an edge of D₂, and there are no edges from D₂ to D₁
We state the key lemma for all directed walks from x to y in the dijoin: a walk between vertices in D₁ stays in D₁, a walk between vertices in D₂ stays in D₂, and no walk goes from D₂ to D₁. We proceed by induction on the transitive closure of the adjacency relation. In the base case of a single edge x → y, the claim follows directly from the definition of the dijoin: an edge between vertices in V is by definition an edge in D₁, an edge between vertices in W is an edge in D₂, and edges from W to V are defined to be false.
uses
Relation.TransGen.singlehave key : ∀ x y, Relation.TransGen (digraph_dijoin D₁ D₂).Adj x y → (∀ a b, x = .inl a → y = .inl b → Relation.TransGen D₁.Adj a b) ∧ (∀ a b, x = .inr a → y = .inr b → Relation.TransGen D₂.Adj a b) ∧ (∀ a b, x = .inr a → y = .inl b → False) := by intro x y h induction h with | single hxy => refine ⟨?_, ?_, ?_⟩ <;> rintro a b rfl rfl · exact .single hxy · exact .single hxy · exact hxy
The key lemma holds for all directed walks in the dijoin: walks between vertices in D₁ stay in D₁, walks between vertices in D₂ stay in D₂, and no walk goes from D₂ to D₁
For the inductive step, suppose the claim holds for a walk from x to b, and consider extending it by an edge b → c. We split into the three required assertions and analyze whether the intermediate vertex b belongs to V or W: 1. If x, c ∈ V: if b ∈ V, the walk from x to b lies in D₁ by the induction hypothesis, and the edge b → c is in D₁, so the walk extends in D₁; if b ∈ W, the edge b → c would go from W to V, which is impossible. 2. If x, c ∈ W: if b ∈ V, the walk from x to b would go from W to V, impossible by the induction hypothesis; if b ∈ W, the walk from x to b lies in D₂ by the induction hypothesis, and b → c is in D₂, so the walk extends in D₂. 3. If x ∈ W and c ∈ V: if b ∈ V, the walk from x to b goes from W to V, impossible by the induction hypothesis; if b ∈ W, the edge b → c goes from W to V, which is impossible by definition.
uses
Relation.TransGen.tail,False.elim| @tail b c _ hbc ih => obtain ⟨ih1, ih2, ih3⟩ := ih refine ⟨?_, ?_, ?_⟩ <;> rintro a c' rfl rfl · rcases b with b | b · exact .tail (ih1 a b rfl rfl) hbc · exact hbc.elim · rcases b with b | b · exact (ih3 a b rfl rfl).elim · exact .tail (ih2 a b rfl rfl) hbc · rcases b with b | b · exact ih3 a b rfl rfl · exact hbcThe dijoin of D₁ and D₂ is acyclic
To show acyclicity of the dijoin, suppose for contradiction that there is a directed cycle from some vertex x to itself. We case split on whether x belongs to V or W: if x = Sum.inl a for a ∈ V, the key lemma implies that the cycle is a directed walk from a to a entirely in D₁, contradicting the acyclicity of D₁; if x = Sum.inr a for a ∈ W, the key lemma implies that the cycle is a directed walk from a to a entirely in D₂, contradicting the acyclicity of D₂.
intro x hx rcases x with a | a · exact h₁ a ((key _ _ hx).1 a a rfl rfl) · exact h₂ a ((key _ _ hx).2.1 a a rfl rfl)
Relation.TransGen.single- A single step of a relation implies its transitive closure
Relation.TransGen.tail- A transitive closure relation can be extended by a step at the end
False.elim- From False, anything follows
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_is_acyclic_dijoin {V W : Type*} (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_acyclic D₁) (h₂ : digraph_is_acyclic D₂) : digraph_is_acyclic (digraph_dijoin D₁ D₂) := by have key : ∀ x y, Relation.TransGen (digraph_dijoin D₁ D₂).Adj x y → (∀ a b, x = .inl a → y = .inl b → Relation.TransGen D₁.Adj a b) ∧ (∀ a b, x = .inr a → y = .inr b → Relation.TransGen D₂.Adj a b) ∧ (∀ a b, x = .inr a → y = .inl b → False) := by intro x y h induction h with | single hxy => refine ⟨?_, ?_, ?_⟩ <;> rintro a b rfl rfl · exact .single hxy · exact .single hxy · exact hxy | @tail b c _ hbc ih => obtain ⟨ih1, ih2, ih3⟩ := ih refine ⟨?_, ?_, ?_⟩ <;> rintro a c' rfl rfl · rcases b with b | b · exact .tail (ih1 a b rfl rfl) hbc · exact hbc.elim · rcases b with b | b · exact (ih3 a b rfl rfl).elim · exact .tail (ih2 a b rfl rfl) hbc · rcases b with b | b · exact ih3 a b rfl rfl · exact hbc intro x hx rcases x with a | a · exact h₁ a ((key _ _ hx).1 a a rfl rfl) · exact h₂ a ((key _ _ hx).2.1 a a rfl rfl)