digraph_linear_arc_dominated_unique_common_successor
Every arc of a finite loopless linear arc-dominated digraph has exactly one common successor; regularity and orientation are not required.
Statement
theorem digraph_linear_arc_dominated_unique_common_successor (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (hlinear : ∀ u v, u ≠ v → ∀ a b, D.Adj a u → D.Adj a v → D.Adj b u → D.Adj b v → a = b) (u v : α) (huv : D.Adj u v) : ∃! w, D.Adj u w ∧ D.Adj v w
- Source
- General zero-overlap duality route for OP-110; exhaustive small checks in experiment 12675.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- digraph_linear_arc_dominated_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem at outdegree d+2 for oriented linear arc-dominated digraphs.
The proof, explained
By arc-domination, every arc e = (x, y) has a chosen common predecessor pred(e), giving rise to a shift map f(e) = (pred(e), x) on the finite set of arcs. Linearity and looplessness guarantee that f is injective: if two arcs had the same image but different targets, their source and chosen predecessor would be distinct common predecessors of those targets, which linearity would force to coincide and create an impossible self-loop. By the pigeonhole principle on finite sets, f is surjective, so the given arc (u, v) is in the image of f and its preimage provides a common successor. Finally, uniqueness of the common successor follows by linearity and looplessness through an analogous argument.
Define the set of arcs and a self-map f on arcs shifting each arc (x, y) to (pred(x, y), x), where pred(x, y) is a common predecessor of x and y.
By arc-domination, for every arc e = (x, y) there exists a vertex dominating both x and y. Using classical choice (`Classical.choose`), we select such a predecessor pred(e), which satisfies pred(e) → x and pred(e) → y (`Classical.choose_spec`). We then define f(e) = (pred(e), x), which is an arc because pred(e) → x.
uses
Classical.choose,Classical.choose_specclassical let Arc := {e : α × α // D.Adj e.1 e.2} let pred : Arc → α := fun e => Classical.choose (hdom e.val.1 e.val.2 e.property) have hpred : ∀ e : Arc, D.Adj (pred e) e.val.1 ∧ D.Adj (pred e) e.val.2 := by intro e exact Classical.choose_spec (hdom e.val.1 e.val.2 e.property) let f : Arc → Arc := fun e => ⟨(pred e, e.val.1), (hpred e).1⟩
The shift map f on arcs is injective.
Assume f(e) = f(k) for two arcs e and k. Comparing components (`congrArg`), we have pred(e) = pred(k) and e₁ = k₁. To show e = k (`Subtype.ext`, `Prod.ext`), it remains to show e₂ = k₂. Suppose for contradiction that e₂ ≠ k₂. Then both e₁ and pred(e) are common predecessors of e₂ and k₂ (since e₁ → e₂, e₁ = k₁ → k₂, pred(e) → e₂, and pred(e) = pred(k) → k₂). By linearity, e₁ = pred(e). But pred(e) → e₁ by construction, so e₁ → e₁, contradicting the assumption that D has no self-loops (`hloop`). Thus e₂ = k₂, so e = k.
uses
congrArg,Subtype.ext,Prod.exthave hinj : Function.Injective f := by intro e k h have hp : pred e = pred k := congrArg (fun z : Arc => z.val.1) h have ht : e.val.1 = k.val.1 := congrArg (fun z : Arc => z.val.2) h apply Subtype.ext apply Prod.ext · exact ht · by_contra hne have hk : D.Adj e.val.1 k.val.2 := by simpa [ht] using k.property have hpk : D.Adj (pred e) k.val.2 := by simpa [hp] using (hpred k).2 have heq : e.val.1 = pred e := hlinear e.val.2 k.val.2 hne e.val.1 (pred e) e.property hk (hpred e).2 hpk exact hloop e.val.1 (by simpa [← heq] using (hpred e).1)
The shift map f on arcs is surjective.
Since the vertex set α is finite, the subtype of arcs is also finite. Any injective endofunction on a finite type is surjective (`Finite.surjective_of_injective`).
uses
Finite.surjective_of_injectivehave hsurj : Function.Surjective f := Finite.surjective_of_injective hinjThe given arc (u, v) has a common successor.
By surjectivity of f, there exists an arc e such that f(e) = (u, v). Matching components (`congrArg`), pred(e) = u and e₁ = v. Since pred(e) → e₂ and e₁ → e₂, we obtain u → e₂ and v → e₂. Hence e₂ is a common successor of u and v.
uses
congrArgobtain ⟨e, he⟩ := hsurj ⟨(u, v), huv⟩ have hp : pred e = u := congrArg (fun z : Arc => z.val.1) he have ht : e.val.1 = v := congrArg (fun z : Arc => z.val.2) he have h1 : D.Adj u e.val.2 := by simpa [hp] using (hpred e).2 have h2 : D.Adj v e.val.2 := by simpa [ht] using e.property refine ⟨e.val.2, ⟨h1, h2⟩, ?_⟩
The common successor of u and v is unique.
Let w be any common successor of u and v, so u → w and v → w. Suppose for contradiction that w ≠ e₂. Then both u and v are common predecessors of the two distinct vertices w and e₂. By linearity, this requires u = v. However, u → v is an arc in D, so u = v implies the self-loop u → u, contradicting looplessness (`hloop`). Therefore w = e₂.
intro w hw by_contra hne have heq : u = v := hlinear w e.val.2 hne u v hw.1 h1 hw.2 h2 exact hloop u (by simpa [← heq] using huv)
Classical.choose- Given a proof that an element with property P exists, returns such an element.
Classical.choose_spec- The witness selected by Classical.choose satisfies the property P.
congrArg- Functions preserve equality: if a = b, then f(a) = f(b).
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
Prod.ext- Two ordered pairs are equal if their first components are equal and their second components are equal.
Finite.surjective_of_injective- An injective function from a finite type to itself is surjective.
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_linear_arc_dominated_unique_common_successor (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (hlinear : ∀ u v, u ≠ v → ∀ a b, D.Adj a u → D.Adj a v → D.Adj b u → D.Adj b v → a = b) (u v : α) (huv : D.Adj u v) : ∃! w, D.Adj u w ∧ D.Adj v w := by classical let Arc := {e : α × α // D.Adj e.1 e.2} let pred : Arc → α := fun e => Classical.choose (hdom e.val.1 e.val.2 e.property) have hpred : ∀ e : Arc, D.Adj (pred e) e.val.1 ∧ D.Adj (pred e) e.val.2 := by intro e exact Classical.choose_spec (hdom e.val.1 e.val.2 e.property) let f : Arc → Arc := fun e => ⟨(pred e, e.val.1), (hpred e).1⟩ have hinj : Function.Injective f := by intro e k h have hp : pred e = pred k := congrArg (fun z : Arc => z.val.1) h have ht : e.val.1 = k.val.1 := congrArg (fun z : Arc => z.val.2) h apply Subtype.ext apply Prod.ext · exact ht · by_contra hne have hk : D.Adj e.val.1 k.val.2 := by simpa [ht] using k.property have hpk : D.Adj (pred e) k.val.2 := by simpa [hp] using (hpred k).2 have heq : e.val.1 = pred e := hlinear e.val.2 k.val.2 hne e.val.1 (pred e) e.property hk (hpred e).2 hpk exact hloop e.val.1 (by simpa [← heq] using (hpred e).1) have hsurj : Function.Surjective f := Finite.surjective_of_injective hinj obtain ⟨e, he⟩ := hsurj ⟨(u, v), huv⟩ have hp : pred e = u := congrArg (fun z : Arc => z.val.1) he have ht : e.val.1 = v := congrArg (fun z : Arc => z.val.2) he have h1 : D.Adj u e.val.2 := by simpa [hp] using (hpred e).2 have h2 : D.Adj v e.val.2 := by simpa [ht] using e.property refine ⟨e.val.2, ⟨h1, h2⟩, ?_⟩ intro w hw by_contra hne have heq : u = v := hlinear w e.val.2 hne u v hw.1 h1 hw.2 h2 exact hloop u (by simpa [← heq] using huv)