digraph_local_outneighborhood_cycle
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
- 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…
- digraph_finite_predecessor_closed_set_cycleA nonempty finite predecessor-closed subset of a loopless digraph contains a directed cycle.
- Used by 4
- 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.
- digraph_trianglefree_weighted_overlap_cycle_packing_stepFor a loopless oriented arc-dominated digraph of directed girth at least four, the k-cycle theorem at outdegree d implies a (k+1)-cycle…
- digraph_small_overlap_arc_dominated_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for oriented arc-dominated digraphs of minimum outdegree at least d+2…
- digraph_girth_weighted_overlap_cycle_packing_stepFor a loopless oriented arc-dominated digraph of directed girth at least g, the k-cycle theorem at outdegree d implies a (k+1)-cycle…
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.
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.
uses
List.nodup_reverse.mpr,List.isChain_reverse.mprobtain ⟨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
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.
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]⟩
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.
uses
Finset.mem_filter.mphave 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⟩
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.
uses
digraph_finite_predecessor_closed_set_cycle,in504_reverse_cycle,Finset.mem_filter.mpobtain ⟨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
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.
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