digraph_dijoin_reverse_eq_inverts
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.
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.
ext x yThe 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).
uses
digraph_dijoin,digraph_reverse,digraph_invertrcases 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
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.
/-- 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]