AFTD Auto-Formalizing Theoretical Domains

digraph_dominated_arcs_in_neighborhood_cycle

theoremverified

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.

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

    lines 9–16

      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⟩
  2. 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.

    lines 17–25

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

    lines 26–40

    uses not_injective_infinite_finite, lt_trichotomy

      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
  4. 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.

    lines 41–52

    uses Nat.find, Nat.find_spec, Nat.find_min, lt_trichotomy

      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⟩
  5. 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.

    lines 53–61

      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
  6. 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.

    lines 62–74

    uses List.nodup_map_iff_inj_on, List.nodup_range, List.mem_range, Subtype.ext

      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
  7. 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].

    lines 75–85

    uses List.isChain_iff_getElem

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

    lines 86–103

    uses List.head?_map, List.head?_range, List.getLast?_map, List.getLast?_range

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

    lines 104–108

    uses List.mem_toFinset, List.mem_map.mp

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

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