AFTD Auto-Formalizing Theoretical Domains

digraph_dijoin_reverse_eq_inverts

theoremverified

The dijoin D̄₁ → D̄₂ equals D₁ → D₂ after inverting the two vertex sets Set.range Sum.inl and Set.range Sum.inr.

Statement

theorem digraph_dijoin_reverse_eq_inverts {V W : Type*} (D₁ : Digraph V) (D₂ : Digraph W) :
    digraph_dijoin (digraph_reverse D₁) (digraph_reverse D₂) =
      digraph_invert (digraph_invert (digraph_dijoin D₁ D₂) (Set.range Sum.inl))
        (Set.range Sum.inr)
Source
step towards tournament_dijoin_inversion_number_symm
Verified
21 Oct 2026
Axioms
Quot.soundpropext
Built on 3
  • digraph_reverseThe reverse D̄ of a digraph D: the digraph on the same vertices with every arc turned around.
  • 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_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…

The proof, explained

The proof proceeds by extensionality on directed graphs, reducing the identity to checking that both graphs agree on directed edges between any two vertices x, y ∈ V ⊕ W. A case analysis on whether x and y lie in the left component V or the right component W yields four subcases. In each case, simplifying with the definitions of dijoin, graph reversal, and vertex-set inversion confirms that edges within each component are reversed while edges between the components remain unchanged.

  1. Two digraphs on V ⊕ W are equal if they have the same directed edges between any pair of vertices x, y ∈ V ⊕ W.

    By extensionality for directed graphs, two digraphs on the same vertex type are identical if their adjacency relations are logically equivalent for every pair of vertices x and y.

    line 6

      ext x y
  2. The adjacency relations of the reversed dijoin and the doubly inverted dijoin coincide on all pairs of vertices.

    We perform a case analysis on whether x and y belong to V (Sum.inl) or W (Sum.inr), and simplify each case using the definitions of digraph_dijoin, digraph_reverse, and digraph_invert: - For x, y ∈ V, inverting on the range of Sum.inl reverses the edge direction just as digraph_reverse does, while inverting on the range of Sum.inr has no effect. - For x, y ∈ W, inverting on the range of Sum.inr reverses the edge direction just as digraph_reverse does, while the inversion on the range of Sum.inl has no effect. - For cross-edges with x ∈ V and y ∈ W (or x ∈ W and y ∈ V), neither vertex set contains both endpoints, so neither inversion changes anything; edges from V to W remain present (True) and edges from W to V remain absent (False).

    lines 7–8

    uses digraph_dijoin, digraph_reverse, digraph_invert

      rcases x with a | a <;> rcases y with b | b <;>
        simp [digraph_dijoin, digraph_reverse, digraph_invert]
digraph_dijoin
The directed join of two digraphs D₁ and D₂, which places all vertices of D₁ and D₂ into a disjoint union V ⊕ W, preserves edges within each component, directs an edge from every vertex in V to every vertex in W, and includes no edges from W to V.
digraph_reverse
The reversal of a digraph D, which replaces every directed edge y → x with an edge x → y.
digraph_invert
The inversion of a digraph D on a vertex subset X, which reverses the direction of all edges whose endpoints both lie in X, while leaving all other edges unchanged.

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

/-- The dijoin D̄₁ → D̄₂ is equal to the dijoin D₁ → D₂ with V(D₁) and V(D₂) inverted. -/theorem digraph_dijoin_reverse_eq_inverts {V W : Type*} (D₁ : Digraph V) (D₂ : Digraph W) :    digraph_dijoin (digraph_reverse D₁) (digraph_reverse D₂) =      digraph_invert (digraph_invert (digraph_dijoin D₁ D₂) (Set.range Sum.inl))        (Set.range Sum.inr) := by  ext x y  rcases x with a | a <;> rcases y with b | b <;>    simp [digraph_dijoin, digraph_reverse, digraph_invert]
See it in the graphDiscuss this resultChallenge it