AFTD Auto-Formalizing Theoretical Domains

digraph_is_acyclic_dijoin

theoremverified

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

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

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

    lines 4–14

    uses Relation.TransGen.single

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

    lines 15–26

    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 hbc
  3. The 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₂.

    lines 27–30

      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

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