AFTD Auto-Formalizing Theoretical Domains

digraph_cross_boundary_predecessor

theoremverified

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.

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

    lines 2–4

      obtain ⟨x, hvx, hx⟩ := hv
      obtain ⟨w, hwv, hwx⟩ := hdom v x hvx
      refine ⟨w, hwv, ?_⟩
  2. 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).

    lines 5–6

      by_cases h : p w = p v
      · exact ⟨x, hwx, fun he => hx (h.symm.trans he)⟩
  3. 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).

    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

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