digraph_dominated_arcs_in_neighborhood_cycle
In a finite loopless digraph where every vertex has positive outdegree and every arc has a common in-neighbor, the in-neighborhood of every vertex contains a directed cycle.
Statement
theorem digraph_dominated_arcs_in_neighborhood_cycle (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hout : ∀ v, ∃ w, D.Adj v w) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) : ∀ a, ∃ C : Finset α, digraph_directed_cycle_on D C ∧ ∀ v ∈ C, D.Adj v a
- Source
- The in-neighborhood reduction from arXiv:1805.02999, Section 3, Claim 1, for the minimum-counterexample route to OP-110.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
The proof, explained
To find a directed cycle in the in-neighborhood S of a vertex a, we first show that every vertex in S has an in-neighbor that also belongs to S, using the dominated arcs hypothesis. We then construct an infinite backward walk in S by repeatedly choosing in-neighbors. Because the digraph is finite, the pigeonhole principle guarantees a repeated vertex; the first such repetition yields a simple directed cycle of length at least 2 entirely contained in S.
The in-neighborhood S of vertex a is nonempty, and every vertex in S has an in-neighbor that also belongs to S.
Since every vertex has positive outdegree, a has an out-neighbor b, forming an arc a → b. By the dominated arcs hypothesis, this arc has a common in-neighbor w₀, which must be adjacent to both a and b; thus w₀ lies in the in-neighborhood S = {x | D.Adj x a}. Moreover, for any s ∈ S, the arc s → a must likewise have a common in-neighbor w, meaning w is adjacent to s and to a. Hence w is an in-neighbor of s that also lies in S.
intro a obtain ⟨b, hab⟩ := hout a obtain ⟨w0, hw0a, -⟩ := hdom a b hab let S := {x : α // D.Adj x a} have hS : ∀ s : S, ∃ t : S, D.Adj t.1 s.1 := by intro ⟨s, hs⟩ obtain ⟨w, hw1, hw2⟩ := hdom s a hs exact ⟨⟨w, hw2⟩, hw1⟩
There exists an infinite sequence x : ℕ → S such that x(t + 1) has an arc to x(t) for every t.
We define a transition function step : S → S choosing an in-neighbor in S for each vertex in S. Starting from s₀ = w₀, we define x(t) = step^[t](s₀) by iterating this step function. By Function.iterate_succ_apply', x(t + 1) = step(x(t)), which guarantees an arc from x(t + 1) to x(t) for every t.
uses
Function.iterate_succ_apply'let step : S → S := fun s => (hS s).choose have hstep : ∀ s : S, D.Adj (step s).1 s.1 := fun s => (hS s).choose_spec let s0 : S := ⟨w0, hw0a⟩ let x : ℕ → S := fun t => step^[t] s0 have hxstep : ∀ t, x (t + 1) = step (x t) := fun t => Function.iterate_succ_apply' step t s0 have hxadj : ∀ t, D.Adj (x (t + 1)).1 (x t).1 := by intro t rw [hxstep] exact hstep (x t)
The sequence x is not injective, so there exist indices m < n such that x(m) = x(n).
Because ℕ is infinite and S is finite, the pigeonhole principle (not_injective_infinite_finite) implies that x cannot be injective. If there were no pair of indices with m < n and x(m) = x(n), then trichotomy (lt_trichotomy) would imply that x is injective, a contradiction.
uses
not_injective_infinite_finite,lt_trichotomyhave hninj : ¬ Function.Injective x := not_injective_infinite_finite x have hex : ∃ n, ∃ m < n, x m = x n := by by_contra h apply hninj intro u v huv rcases lt_trichotomy u v with hlt | heq | hgt · exfalso have : ¬ ∃ m < v, x m = x v := fun ⟨m, hm, hx⟩ => h ⟨v, m, hm, hx⟩ push Not at this exact this u hlt huv · exact heq · exfalso have : ¬ ∃ m < u, x m = x u := fun ⟨m, hm, hx⟩ => h ⟨u, m, hm, hx⟩ push Not at this exact this v hgt huv.symm
Let n be the minimal index where a previous value repeats, x(m) = x(n) with m < n; then x is injective on {0, ..., n - 1}.
We choose n as the least index admitting a repetition using Nat.find, and obtain the earlier index m < n from Nat.find_spec. By minimality (Nat.find_min), no index strictly smaller than n repeats any earlier value. Consequently, by lt_trichotomy, the sequence x is injective when restricted to indices strictly less than n.
uses
Nat.find,Nat.find_spec,Nat.find_min,lt_trichotomyclassical let n := Nat.find hex obtain ⟨m, hmn, hxmn⟩ := Nat.find_spec hex have hmin : ∀ t < n, ¬ ∃ s < t, x s = x t := fun t ht => Nat.find_min hex ht have hinj : ∀ i < n, ∀ j < n, x i = x j → i = j := by intro i hi j hj hij rcases lt_trichotomy i j with hlt | heq | hgt · exfalso exact hmin j hj ⟨i, hlt, hij⟩ · exact heq · exfalso exact hmin i hi ⟨j, hgt, hij.symm⟩
The cycle length k = n - m satisfies 2 ≤ k.
Since m < n, linear arithmetic shows k = n - m ≠ 0. If k were 1, then n = m + 1, so x(m + 1) = x(m). But there is an arc from x(m + 1) to x(m), which would produce a self-loop at x(m), contradicting the assumption that D has no loops (hloop). Hence k ≥ 2.
have hk : n - m ≠ 0 := by omega have hk2 : 2 ≤ n - m := by by_contra! h have hk1 : n - m = 1 := by omega have hnm1 : n = m + 1 := by omega have hx1 : x (m + 1) = x m := by rw [← hnm1, hxmn.symm] have hadj := hxadj m rw [hx1] at hadj exact hloop (x m).1 hadj
The list l of length k obtained by reversing the sequence indices contains no duplicate vertices.
We define k = n - m and the list l of length k whose i-th element is c(i) = (x(n - 1 - i)).1, obtained by mapping c over List.range k. By List.nodup_map_iff_inj_on and List.nodup_range, l has no duplicates provided c is injective on List.range k. If c(i) = c(j), the subtype equality Subtype.ext gives x(n - 1 - i) = x(n - 1 - j). Since i, j < k ≤ n, both indices are strictly less than n (List.mem_range). The injectivity of x on {0, ..., n - 1} then forces n - 1 - i = n - 1 - j, hence i = j.
uses
List.nodup_map_iff_inj_on,List.nodup_range,List.mem_range,Subtype.extlet k := n - m let c : ℕ → α := fun i => (x (n - 1 - i)).1 let l : List α := (List.range k).map c have hlen : l.length = k := by simp [l] have hnodup : l.Nodup := by refine (List.nodup_map_iff_inj_on List.nodup_range).mpr ?_ intro i hi j hj hij simp only [List.mem_range] at hi hj have heq : x (n - 1 - i) = x (n - 1 - j) := Subtype.ext hij have hi' : n - 1 - i < n := by omega have hj' : n - 1 - j < n := by omega have : n - 1 - i = n - 1 - j := hinj (n - 1 - i) hi' (n - 1 - j) hj' heq omega
The list l forms a directed chain in D.
By List.isChain_iff_getElem, l is a chain under D.Adj if each element l[i] has an arc to l[i + 1]. By definition, l[i] = x(n - 1 - i) and l[i + 1] = x(n - 1 - (i + 1)). Since n - 1 - i = (n - 1 - (i + 1)) + 1, the step adjacency relation x(t + 1) → x(t) applied at t = n - 1 - (i + 1) gives an arc from l[i] to l[i + 1].
uses
List.isChain_iff_getElemhave hchain : l.IsChain D.Adj := by rw [List.isChain_iff_getElem] intro i hi have hik : i + 1 < k := by simpa [hlen] using hi have h1 : l[i] = c i := by simp [l] have h2 : l[i + 1] = c (i + 1) := by simp [l] rw [h1, h2] dsimp [c] have hrel : n - 1 - i = (n - 1 - (i + 1)) + 1 := by omega rw [hrel] exact hxadj (n - 1 - (i + 1))
The head of l is c(0), the last element is c(k - 1), and there is an arc from c(k - 1) to c(0) closing the cycle.
Since k ≠ 0, evaluating the head and last element of List.range k mapped by c (via List.head?_map, List.head?_range, List.getLast?_map, List.getLast?_range) gives head c(0) and last element c(k - 1). Here c(k - 1) = x(n - 1 - (k - 1)) = x(m) = x(n) = x((n - 1) + 1), while c(0) = x(n - 1). The step adjacency relation x(t + 1) → x(t) at t = n - 1 yields an arc from c(k - 1) to c(0).
uses
List.head?_map,List.head?_range,List.getLast?_map,List.getLast?_rangehave hhead : l.head? = some (c 0) := by rw [List.head?_map, List.head?_range] have : k ≠ 0 := by omega simp [this] have hlast : l.getLast? = some (c (k - 1)) := by rw [List.getLast?_map, List.getLast?_range] have : k ≠ 0 := by omega simp [this] have hadj_last_head : D.Adj (c (k - 1)) (c 0) := by change D.Adj (x (n - 1 - (k - 1))).1 (x (n - 1 - 0)).1 have h1 : n - 1 - (k - 1) = m := by omega have h2 : n - 1 - 0 = n - 1 := by omega rw [h1, h2] have heq : (x m).1 = (x n).1 := by rw [hxmn] rw [heq] have hnrel : n = (n - 1) + 1 := by omega nth_rw 1 [hnrel] exact hxadj (n - 1)
The vertex set of l forms a directed cycle on D, and every vertex in it belongs to the in-neighborhood of a.
We set C = l.toFinset. The list l witnesses digraph_directed_cycle_on D C: it has no duplicates, length at least 2, forms a directed chain, and has an arc from its last element to its head. Finally, every v ∈ C belongs to the list l (List.mem_toFinset), so by List.mem_map.mp it equals (x(n - 1 - i)).1 for some i. Since each x(t) is defined as an element of the subtype S = {x | D.Adj x a}, the vertex v satisfies D.Adj v a.
uses
List.mem_toFinset,List.mem_map.mprefine ⟨l.toFinset, ⟨l, hnodup, by rw [hlen]; exact hk2, rfl, hchain, ⟨c 0, c (k - 1), hhead, hlast, hadj_last_head⟩⟩, ?_⟩ intro v hv rw [List.mem_toFinset] at hv rcases List.mem_map.mp hv with ⟨i, hi, rfl⟩ exact (x (n - 1 - i)).2
Function.iterate_succ_apply'- The (n+1)-st iterate of a function f applied to x equals f applied to the n-th iterate of f at x.
not_injective_infinite_finite- A function from an infinite type to a finite type cannot be injective.
lt_trichotomy- In a linear order, for any two elements a and b, exactly one of a < b, a = b, or b < a holds.
Nat.find- Given a proof that there exists a natural number satisfying a decidable predicate, returns the smallest such number.
Nat.find_spec- The minimal natural number returned by Nat.find satisfies the given predicate.
Nat.find_min- Any natural number strictly smaller than Nat.find does not satisfy the given predicate.
List.nodup_map_iff_inj_on- Mapping a function f over a duplicate-free list yields a duplicate-free list if and only if f is injective on the elements of the list.
List.nodup_range- The list range n = [0, 1, ..., n - 1] contains no duplicate elements.
List.mem_range- A natural number m belongs to List.range n if and only if m < n.
Subtype.ext- Two elements of a subtype are equal if and only if their underlying values are equal.
List.isChain_iff_getElem- A list is a chain under a relation R if and only if R holds between each element and the next.
List.head?_map- The optional head of List.map f l is the result of applying f to the optional head of l.
List.head?_range- The optional head of List.range n is none if n = 0, and some 0 if n > 0.
List.getLast?_map- The optional last element of List.map f l is the result of applying f to the optional last element of l.
List.getLast?_range- The optional last element of List.range n is none if n = 0, and some (n - 1) if n > 0.
List.mem_toFinset- An element belongs to l.toFinset if and only if it belongs to the list l.
List.mem_map.mp- If an element belongs to List.map f l, then it is the image under f of some element of l.
- The directed cycle definition requires a cycle length of at least 2, so the loopless hypothesis is used to rule out a repetition after a single step.
- Because the step relation traces in-neighbors backward (from x(t+1) to x(t)), the cycle list l reverses the indices via c(i) = x(n - 1 - i) so that consecutive list elements follow the forward edge direction.
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_dominated_arcs_in_neighborhood_cycle (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hout : ∀ v, ∃ w, D.Adj v w) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) : ∀ a, ∃ C : Finset α, digraph_directed_cycle_on D C ∧ ∀ v ∈ C, D.Adj v a := by intro a obtain ⟨b, hab⟩ := hout a obtain ⟨w0, hw0a, -⟩ := hdom a b hab let S := {x : α // D.Adj x a} have hS : ∀ s : S, ∃ t : S, D.Adj t.1 s.1 := by intro ⟨s, hs⟩ obtain ⟨w, hw1, hw2⟩ := hdom s a hs exact ⟨⟨w, hw2⟩, hw1⟩ let step : S → S := fun s => (hS s).choose have hstep : ∀ s : S, D.Adj (step s).1 s.1 := fun s => (hS s).choose_spec let s0 : S := ⟨w0, hw0a⟩ let x : ℕ → S := fun t => step^[t] s0 have hxstep : ∀ t, x (t + 1) = step (x t) := fun t => Function.iterate_succ_apply' step t s0 have hxadj : ∀ t, D.Adj (x (t + 1)).1 (x t).1 := by intro t rw [hxstep] exact hstep (x t) have hninj : ¬ Function.Injective x := not_injective_infinite_finite x have hex : ∃ n, ∃ m < n, x m = x n := by by_contra h apply hninj intro u v huv rcases lt_trichotomy u v with hlt | heq | hgt · exfalso have : ¬ ∃ m < v, x m = x v := fun ⟨m, hm, hx⟩ => h ⟨v, m, hm, hx⟩ push Not at this exact this u hlt huv · exact heq · exfalso have : ¬ ∃ m < u, x m = x u := fun ⟨m, hm, hx⟩ => h ⟨u, m, hm, hx⟩ push Not at this exact this v hgt huv.symm classical let n := Nat.find hex obtain ⟨m, hmn, hxmn⟩ := Nat.find_spec hex have hmin : ∀ t < n, ¬ ∃ s < t, x s = x t := fun t ht => Nat.find_min hex ht have hinj : ∀ i < n, ∀ j < n, x i = x j → i = j := by intro i hi j hj hij rcases lt_trichotomy i j with hlt | heq | hgt · exfalso exact hmin j hj ⟨i, hlt, hij⟩ · exact heq · exfalso exact hmin i hi ⟨j, hgt, hij.symm⟩ have hk : n - m ≠ 0 := by omega have hk2 : 2 ≤ n - m := by by_contra! h have hk1 : n - m = 1 := by omega have hnm1 : n = m + 1 := by omega have hx1 : x (m + 1) = x m := by rw [← hnm1, hxmn.symm] have hadj := hxadj m rw [hx1] at hadj exact hloop (x m).1 hadj let k := n - m let c : ℕ → α := fun i => (x (n - 1 - i)).1 let l : List α := (List.range k).map c have hlen : l.length = k := by simp [l] have hnodup : l.Nodup := by refine (List.nodup_map_iff_inj_on List.nodup_range).mpr ?_ intro i hi j hj hij simp only [List.mem_range] at hi hj have heq : x (n - 1 - i) = x (n - 1 - j) := Subtype.ext hij have hi' : n - 1 - i < n := by omega have hj' : n - 1 - j < n := by omega have : n - 1 - i = n - 1 - j := hinj (n - 1 - i) hi' (n - 1 - j) hj' heq omega have hchain : l.IsChain D.Adj := by rw [List.isChain_iff_getElem] intro i hi have hik : i + 1 < k := by simpa [hlen] using hi have h1 : l[i] = c i := by simp [l] have h2 : l[i + 1] = c (i + 1) := by simp [l] rw [h1, h2] dsimp [c] have hrel : n - 1 - i = (n - 1 - (i + 1)) + 1 := by omega rw [hrel] exact hxadj (n - 1 - (i + 1)) have hhead : l.head? = some (c 0) := by rw [List.head?_map, List.head?_range] have : k ≠ 0 := by omega simp [this] have hlast : l.getLast? = some (c (k - 1)) := by rw [List.getLast?_map, List.getLast?_range] have : k ≠ 0 := by omega simp [this] have hadj_last_head : D.Adj (c (k - 1)) (c 0) := by change D.Adj (x (n - 1 - (k - 1))).1 (x (n - 1 - 0)).1 have h1 : n - 1 - (k - 1) = m := by omega have h2 : n - 1 - 0 = n - 1 := by omega rw [h1, h2] have heq : (x m).1 = (x n).1 := by rw [hxmn] rw [heq] have hnrel : n = (n - 1) + 1 := by omega nth_rw 1 [hnrel] exact hxadj (n - 1) refine ⟨l.toFinset, ⟨l, hnodup, by rw [hlen]; exact hk2, rfl, hchain, ⟨c 0, c (k - 1), hhead, hlast, hadj_last_head⟩⟩, ?_⟩ intro v hv rw [List.mem_toFinset] at hv rcases List.mem_map.mp hv with ⟨i, hi, rfl⟩ exact (x (n - 1 - i)).2