digraph_cross_boundary_predecessor
For any bipartition of an arc-dominated digraph, every tail of a crossing arc has an in-neighbor that is also a tail of a crossing arc.
Statement
theorem digraph_cross_boundary_predecessor {α : Type} (D : Digraph α) (p : α → Bool) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (v : α) (hv : ∃ x, D.Adj v x ∧ p v ≠ p x) : ∃ w, D.Adj w v ∧ ∃ y, D.Adj w y ∧ p w ≠ p y
- Source
- Boundary reduction for the minimum-counterexample route to OP-110.
- Verified
- 02 Nov 2026
- Axioms
- none — Lean reports it depends on no axioms
The proof, explained
The theorem is proved by exhibiting an explicit common predecessor. Given that $v$ has an out-neighbor $x$ across the partition ($p(v) \ne p(x)$), the arc-domination hypothesis guarantees a vertex $w$ with directed edges to both $v$ and $x$. By case analysis on whether $p(w) = p(v)$, one of these two edges must cross the boundary: if $p(w) = p(v)$, then $w \to x$ crosses because $p(w) \ne p(x)$; otherwise $p(w) \ne p(v)$, so $w \to v$ crosses.
There exists a common in-neighbor $w$ of $v$ and $x$, and the goal reduces to finding an outgoing crossing arc from $w$.
From the hypothesis that $v$ is the tail of a crossing arc, we obtain a vertex $x$ such that there is an arc $v \to x$ and $p(v) \ne p(x)$ (line 2). By arc-domination applied to the arc $v \to x$, there exists a common predecessor $w$ with arcs $w \to v$ and $w \to x$ (line 3). Selecting $w$ as the witness for the outer existential quantifier reduces the goal to showing that $w$ has an outgoing arc crossing the bipartition (line 4).
obtain ⟨x, hvx, hx⟩ := hv obtain ⟨w, hwv, hwx⟩ := hdom v x hvx refine ⟨w, hwv, ?_⟩
If $w$ and $v$ have the same partition label, then the arc $w \to x$ crosses the partition boundary.
We split into cases on whether $p(w) = p(v)$ (line 5). In the case where $p(w) = p(v)$, the arc $w \to x$ must cross the boundary: if $p(w) = p(x)$, then transitivity with $p(w) = p(v)$ would yield $p(v) = p(x)$, contradicting $p(v) \ne p(x)$. Thus the vertex $x$ witnesses that $w$ has an outgoing crossing arc (line 6).
by_cases h : p w = p v · exact ⟨x, hwx, fun he => hx (h.symm.trans he)⟩
If $w$ and $v$ have different partition labels, then the arc $w \to v$ crosses the partition boundary.
In the remaining case where $p(w) \ne p(v)$, the arc $w \to v$ itself crosses the bipartition, so $v$ directly witnesses that $w$ has an outgoing crossing arc (line 7).
· exact ⟨v, hwv, 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_cross_boundary_predecessor {α : Type} (D : Digraph α) (p : α → Bool) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (v : α) (hv : ∃ x, D.Adj v x ∧ p v ≠ p x) : ∃ w, D.Adj w v ∧ ∃ y, D.Adj w y ∧ p w ≠ p y := by obtain ⟨x, hvx, hx⟩ := hv obtain ⟨w, hwv, hwx⟩ := hdom v x hvx refine ⟨w, hwv, ?_⟩ by_cases h : p w = p v · exact ⟨x, hwx, fun he => hx (h.symm.trans he)⟩ · exact ⟨v, hwv, h⟩