AFTD Auto-Formalizing Theoretical Domains

digraph_local_outneighborhood_cycle

theoremverified

If an out-neighborhood is nonempty and each of its vertices has an out-neighbor inside it, it contains a directed cycle.

Statement

theorem digraph_local_outneighborhood_cycle
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (hloop : ∀ v, ¬ D.Adj v v) (v : α) (hv : ∃ w, D.Adj v w)
    (hcodom : ∀ w, D.Adj v w → ∃ x, D.Adj v x ∧ D.Adj w x) :
    ∃ C : Finset α, digraph_directed_cycle_on D C ∧ ∀ w ∈ C, D.Adj v w
Source
Local-cycle helper for the small-overlap structural route to OP-110.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 4

The proof, explained

The proof reduces the problem of finding a cycle in the out-neighborhood of v to finding a cycle in a predecessor-closed set in the edge-reversed digraph. Since every vertex in the out-neighborhood has an out-neighbor in the out-neighborhood, in the reversed graph every vertex in this set has an in-neighbor. A standard theorem then yields a directed cycle in the reversed graph inside the out-neighborhood, which is reversed back into a directed cycle in the original graph.

  1. A directed cycle in the reversed graph yields a directed cycle in D by reversing the vertex list

    Given a directed cycle in the reversed digraph with vertex list l, reversing the list yields a list with no duplicates (by List.nodup_reverse.mpr), length at least 2, and the same underlying set of vertices. By List.isChain_reverse.mpr, consecutive vertices in the reversed list are connected by edges in D, and the original closing edge between the endpoints connects the new endpoints in D.

    lines 5–13

    uses List.nodup_reverse.mpr, List.isChain_reverse.mpr

      obtain ⟨l, hnodup, hlen, hset, hchain, a, b, ha, hb, hab⟩ := h
      refine ⟨l.reverse, ?_, ?_, ?_, ?_, b, a, ?_, ?_, ?_⟩
      · exact List.nodup_reverse.mpr hnodup
      · simpa using hlen
      · simpa using hset
      · exact List.isChain_reverse.mpr hchain
      · simpa using hb
      · simpa using ha
      · exact hab
  2. Define the reversed digraph R and the out-neighborhood T of v, and show T is nonempty

    Let R be the digraph with reversed edges, and let T be the set of out-neighbors of v in D. Since v has at least one out-neighbor by hv, T is nonempty.

    lines 20–25

      classical
      let R : Digraph α := ⟨fun u w => D.Adj w u⟩
      let T : Finset α := Finset.univ.filter fun w => D.Adj v w
      have hT : T.Nonempty := by
        obtain ⟨w, hw⟩ := hv
        exact ⟨w, by simp [T, hw]⟩
  3. Every vertex in T has an in-neighbor in T with respect to R

    For any w in T, hypothesis hcodom provides an out-neighbor x of w that is also an out-neighbor of v (so x is in T). In the reversed graph R, this out-edge w → x becomes an in-edge x → w, meaning x is an in-neighbor of w in R.

    lines 26–30

    uses Finset.mem_filter.mp

      have hpred : ∀ w ∈ T, ∃ x ∈ T, R.Adj x w := by
        intro w hw
        have h₁ : D.Adj v w := (Finset.mem_filter.mp hw).2
        obtain ⟨x, hvx, hwx⟩ := hcodom w h₁
        exact ⟨x, by simp [T, hvx], hwx⟩
  4. Apply the predecessor-closed cycle theorem in R and reverse the resulting cycle to obtain a cycle in D contained in T

    Applying digraph_finite_predecessor_closed_set_cycle to R and T produces a cycle C in R contained in T. Using in504_reverse_cycle, C is also a directed cycle in D. Since C is contained in T, every vertex in C is an out-neighbor of v.

    lines 31–34

    uses digraph_finite_predecessor_closed_set_cycle, in504_reverse_cycle, Finset.mem_filter.mp

      obtain ⟨C, hC, hsub⟩ := digraph_finite_predecessor_closed_set_cycle α R T hT hloop hpred
      refine ⟨C, in504_reverse_cycle α D C hC, ?_⟩
      intro w hw
      exact (Finset.mem_filter.mp (hsub hw)).2
List.nodup_reverse.mpr
Reversing a list preserves the property of having no duplicate elements
List.isChain_reverse.mpr
A list is a chain for relation R if and only if its reverse is a chain for the flipped relation
in504_reverse_cycle
A directed cycle in the reversed digraph corresponds to a directed cycle in the original digraph on the same vertex set
digraph_finite_predecessor_closed_set_cycle
A finite, loopless directed graph with a nonempty set where every vertex has an in-neighbor contains a directed cycle in that set
Finset.mem_filter.mp
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the filtering predicate

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

private theorem in504_reverse_cycle (α : Type) [DecidableEq α]    (D : Digraph α) (C : Finset α)    (h : digraph_directed_cycle_on ⟨fun u v => D.Adj v u⟩ C) :    digraph_directed_cycle_on D C := by  obtain ⟨l, hnodup, hlen, hset, hchain, a, b, ha, hb, hab⟩ := h  refine ⟨l.reverse, ?_, ?_, ?_, ?_, b, a, ?_, ?_, ?_⟩  · exact List.nodup_reverse.mpr hnodup  · simpa using hlen  · simpa using hset  · exact List.isChain_reverse.mpr hchain  · simpa using hb  · simpa using ha  · exact habtheorem digraph_local_outneighborhood_cycle    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (hloop : ∀ v, ¬ D.Adj v v) (v : α) (hv : ∃ w, D.Adj v w)    (hcodom : ∀ w, D.Adj v w → ∃ x, D.Adj v x ∧ D.Adj w x) :    ∃ C : Finset α, digraph_directed_cycle_on D C ∧ ∀ w ∈ C, D.Adj v w := by  classical  let R : Digraph α := ⟨fun u w => D.Adj w u⟩  let T : Finset α := Finset.univ.filter fun w => D.Adj v w  have hT : T.Nonempty := by    obtain ⟨w, hw⟩ := hv    exact ⟨w, by simp [T, hw]⟩  have hpred : ∀ w ∈ T, ∃ x ∈ T, R.Adj x w := by    intro w hw    have h₁ : D.Adj v w := (Finset.mem_filter.mp hw).2    obtain ⟨x, hvx, hwx⟩ := hcodom w h₁    exact ⟨x, by simp [T, hvx], hwx⟩  obtain ⟨C, hC, hsub⟩ := digraph_finite_predecessor_closed_set_cycle α R T hT hloop hpred  refine ⟨C, in504_reverse_cycle α D C hC, ?_⟩  intro w hw  exact (Finset.mem_filter.mp (hsub hw)).2
See it in the graphDiscuss this resultChallenge it