digraph_common_cycle_core_neighbor_unique
Inside a strongly connected finite set, if every directed cycle contains a fixed core, every vertex has at most one outgoing neighbor and at most one incoming neighbor in that core.
Statement
theorem digraph_common_cycle_core_neighbor_unique (α : Type) [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (T S : Finset α) (hST : S ⊆ T) (hloop : ∀ v, ¬ D.Adj v v) (hstrong : ∀ u ∈ T, ∀ v ∈ T, ∃ p : List α, digraph_is_directed_path D p u v ∧ ∀ z ∈ p, z ∈ T) (hcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on D C → S ⊆ C) : ∀ x ∈ T, (S.filter fun y => D.Adj x y).card ≤ 1 ∧ (S.filter fun y => D.Adj y x).card ≤ 1
- Source
- Common-cycle core argument for the oriented twenty-cut profile; experiment 26272 checks all oriented graphs through five vertices.
- Verified
- 14 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_is_directed_pathA directed path from u to v in a digraph D is a list of vertices p forming a directed chain in D with no duplicate vertices, starting at u…
- Used by 3
- digraph_17_shared_target_forces_two_cyclesThe normalized oriented seventeen-vertex shared-target configuration with three designated parents contains two disjoint cycles, assuming…
- digraph_16_shared_target_forces_two_cyclesThe normalized oriented sixteen-vertex shared-target configuration contains two disjoint cycles, assuming the displayed two-cycle criterion.
- digraph_common_cycle_core_outside_injectionIn a strongly connected finite vertex set, suppose all directed cycles contain a core K and every vertex in a subset S of K has at least…
The proof, explained
To show that every vertex x ∈ T has at most one outgoing neighbor in the core S, assume for contradiction that x has two distinct outgoing neighbors a, b ∈ S. By strong connectivity, there is a directed path p in T from a to x. If b lies on p, the subpath from b to x closed with the edge x → b gives a directed cycle in T that omits a; if b does not lie on p, the path p closed with x → a gives a directed cycle in T that omits b. Either case contradicts the hypothesis that every directed cycle in T contains the core S. Applying this uniqueness of outgoing neighbors to the reversed digraph immediately yields the dual bound for incoming neighbors.
A directed path with distinct endpoints, together with a closing edge from its end back to its start, forms a directed cycle on its vertex set.
Deconstructing the directed path yields a duplicate-free chain of vertices starting at a and ending at b. By case analysis on the list of vertices, the path cannot be empty (since its head is a) and cannot have length 1 (since that would force a = b, contradicting a ≠ b), so its length is at least 2. Together with the closing edge from b to a, this satisfies the definition of a directed cycle.
obtain ⟨hchain, hnodup, hhead, hlast⟩ := hpath have hlen : 2 ≤ p.length := by cases p with | nil => simp at hhead | cons z zs => cases zs with | nil => simp_all | cons w ws => simp exact ⟨p, hnodup, hlen, rfl, hchain, a, b, hhead, hlast, hclose⟩
To show that any vertex x ∈ T has at most one outgoing neighbor in S, it suffices to derive a contradiction from the existence of distinct neighbors a, b ∈ S with x → a and x → b.
Using Finset.card_le_one.mpr, we assume for contradiction that there exist distinct vertices a, b ∈ S such that D.Adj x a and D.Adj x b hold (extracted via Finset.mem_filter.mp). Since the digraph has no self-loops, x → a implies a ≠ x, and x → b implies b ≠ x.
uses
Finset.card_le_one.mpr,Finset.mem_filter.mpclassical intro x hx apply Finset.card_le_one.mpr intro a ha b hb have haS : a ∈ S := (Finset.mem_filter.mp ha).1 have hbS : b ∈ S := (Finset.mem_filter.mp hb).1 have hxa : D.Adj x a := (Finset.mem_filter.mp ha).2 have hxb : D.Adj x b := (Finset.mem_filter.mp hb).2 by_contra hab have hax : a ≠ x := by intro h; subst a; exact (hloop x) hxa have hbx : b ≠ x := by intro h; subst b; exact (hloop x) hxb
There exists a directed path p in T from a to x.
Since a ∈ S ⊆ T and x ∈ T, the strong connectivity hypothesis on T provides a directed path p from a to x entirely contained within T. We decompose p into its chain property, duplicate-free property, head a, and last element x.
obtain ⟨p,hpath,hpT⟩ := hstrong a (hST haS) x hx obtain ⟨hchain, hnodup, hhead, hlast⟩ := hpath
When b lies on p, the path decomposes into a prefix starting at a followed by a suffix starting at b that does not contain a.
We split into cases on whether b ∈ p. Using List.mem_iff_append.mp, p can be written as pre ++ b :: tail. If pre were empty, the head of p would be b, forcing a = b, which contradicts a ≠ b. Hence pre = a :: zs. Because p has no duplicates (List.nodup_append.mp), the suffix b :: tail is duplicate-free and cannot contain a.
uses
List.mem_iff_append.mp,List.nil_append,List.head?_cons,Option.some.injEq,List.nodup_append.mpby_cases hbp : b ∈ p · obtain ⟨pre,tail,hp⟩ := List.mem_iff_append.mp hbp cases pre with | nil => simp only [List.nil_append, List.head?_cons, Option.some.injEq] at hp hhead have : a = b := by simpa [hp] using hhead.symm exact hab this | cons z zs => have hz : z = a := by rw [hp] at hhead simpa using hhead subst z have hnodup' : ((a :: zs) ++ b :: tail).Nodup := by simpa [hp] using hnodup have hsufnodup : (b :: tail).Nodup := (List.nodup_append.mp hnodup').2.1 have hnot : a ∉ b :: tail := by intro ha' exact (List.nodup_append.mp hnodup').2.2 a (by simp) a ha' rfl
When b lies on p, the suffix b :: tail together with x → b forms a directed cycle in T that omits a, contradicting that every cycle contains S.
The suffix b :: tail inherits the edge chain property from p and ends at x, making it a directed path from b to x. Closing this path with the edge x → b via in833_path_close_cycle yields a directed cycle whose vertices lie in T. By the core hypothesis, this cycle must contain S and therefore must contain a, which contradicts the fact that a is not in b :: tail.
uses
List.getLast?_append_cons,in833_path_close_cycle,List.mem_append_righthave hchain' : ((a :: zs) ++ b :: tail).IsChain D.Adj := by simpa [hp] using hchain have hsufchain : (b :: tail).IsChain D.Adj := hchain'.right_of_append have hsuflast : (b :: tail).getLast? = some x := by rw [hp, List.getLast?_append_cons] at hlast exact hlast have hsufpath : digraph_is_directed_path D (b :: tail) b x := ⟨hsufchain, hsufnodup, by simp, hsuflast⟩ have hcycle := in833_path_close_cycle D (b :: tail) b x hsufpath hbx hxb have hsub : (b :: tail).toFinset ⊆ T := by intro y hy have hy' : y ∈ b :: tail := by simpa using hy apply hpT y rw [hp] exact List.mem_append_right _ hy' have hc := hcore (b :: tail).toFinset hsub hcycle haS exact hnot (by simpa using hc)
When b does not lie on p, closing p with x → a forms a directed cycle in T that omits b, again contradicting the core hypothesis.
Closing the full path p from a to x with the edge x → a via in833_path_close_cycle yields a directed cycle on the vertices of p, all of which belong to T. By the core hypothesis, this cycle must contain S, and in particular must contain b. But b is not on p, a contradiction. This completes both branches of the case analysis, establishing a = b.
uses
in833_path_close_cycle· have hcycle := in833_path_close_cycle D p a x ⟨hchain,hnodup,hhead,hlast⟩ hax hxa have hsub : p.toFinset ⊆ T := by intro y hy apply hpT y simpa using hy have hc := hcore p.toFinset hsub hcycle hbS exact hbp (by simpa using hc)
Any directed cycle in the reversed digraph corresponds to a directed cycle in D on the same vertex set.
Reversing the list of vertices of a cycle in the reversed digraph preserves non-duplication (List.nodup_reverse.mpr), length, and vertex set. By List.isChain_reverse.mpr, an edge chain in the reversed digraph becomes an edge chain in D. The original closing edge connects the reversed endpoints, producing a directed cycle 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
Every vertex x ∈ T has at most one outgoing neighbor in S.
Applying the uniqueness lemma in833_core_out_unique directly gives that the number of outgoing neighbors of x in S is at most 1.
uses
in833_core_out_uniqueclassical have hout := in833_core_out_unique α D T S hST hloop hstrong hcoreThe reversed digraph E is loopless, strongly connected on T, and every cycle in T contains the core S.
Digraph E has no loops because D has none. For any u, v ∈ T, reversing a path from v to u in D provides a directed path from u to v in E (using List.isChain_reverse.mpr). Finally, any cycle in E within T reverses via in833_core_reverse_cycle to a cycle in D, which must contain S by the core hypothesis.
uses
List.isChain_reverse.mpr,in833_core_reverse_cyclelet E : Digraph α := ⟨fun u v => D.Adj v u⟩ have hEloop : ∀ v, ¬ E.Adj v v := hloop have hEstrong : ∀ u ∈ T, ∀ v ∈ T, ∃ p : List α, digraph_is_directed_path E p u v ∧ ∀ z ∈ p, z ∈ T := by intro u hu v hv obtain ⟨p,hp,hT⟩ := hstrong v hv u hu obtain ⟨hc,hn,hh,hl⟩ := hp refine ⟨p.reverse, ?_, ?_⟩ · refine ⟨?_, by simpa using hn, ?_, ?_⟩ · exact List.isChain_reverse.mpr hc · simpa using hl · simpa using hh · intro z hz apply hT z simpa using hz have hEcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on E C → S ⊆ C := by intro C hsub hc exact hcore C hsub (in833_core_reverse_cycle D C hc)
Every vertex x ∈ T has at most one incoming neighbor in S, completing the theorem.
Applying in833_core_out_unique to the reversed digraph E shows that x has at most one outgoing neighbor in S in E. Since outgoing edges in E correspond to incoming edges in D, x has at most one incoming neighbor in S, which establishes the second conjunction.
uses
in833_core_out_uniquehave hin := in833_core_out_unique α E T S hST hEloop hEstrong hEcore intro x hx refine ⟨hout x hx, ?_⟩ simpa [E] using hin x hx
Finset.card_le_one.mpr- A finite set has cardinality at most 1 if any two of its elements are equal.
Finset.mem_filter.mp- An element belongs to a filtered set if and only if it belongs to the original set and satisfies the filtering predicate.
List.mem_iff_append.mp- An element belongs to a list if and only if the list can be split into a prefix and a suffix around that element.
List.nil_append- Concatenating the empty list to any list yields the original list.
List.head?_cons- The head of a list constructed by prepending an element is that element.
Option.some.injEq- The constructor 'some' is injective on optional values.
List.nodup_append.mp- If the concatenation of two lists has no duplicates, then both lists have no duplicates and they are disjoint.
List.getLast?_append_cons- The last element of a concatenation ending in a non-empty list is the last element of that suffix.
List.mem_append_right- An element belonging to a suffix also belongs to the concatenated list.
in833_path_close_cycle- A directed path with distinct endpoints, together with a closing edge from end to start, forms a directed cycle on its vertex set.
List.nodup_reverse.mpr- Reversing a list preserves the property of having no duplicate elements.
List.isChain_reverse.mpr- A chain under a relation reverses to a chain under the transposed relation.
in833_core_reverse_cycle- A directed cycle in the reversed digraph on a vertex set is also a directed cycle in the original digraph on that set.
in833_core_out_unique- Inside a strongly connected subset of a loopless digraph where every cycle contains a core S, every vertex has at most one outgoing neighbor in S.
- The theorem establishes the bound for incoming neighbors by dualizing the result for outgoing neighbors via digraph edge reversal.
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.
set_option maxHeartbeats 3000000set_option maxRecDepth 4096private theorem in833_path_close_cycle {α : Type} [DecidableEq α] (D : Digraph α) (p : List α) (a b : α) (hpath : digraph_is_directed_path D p a b) (hne : a ≠ b) (hclose : D.Adj b a) : digraph_directed_cycle_on D p.toFinset := by obtain ⟨hchain, hnodup, hhead, hlast⟩ := hpath have hlen : 2 ≤ p.length := by cases p with | nil => simp at hhead | cons z zs => cases zs with | nil => simp_all | cons w ws => simp exact ⟨p, hnodup, hlen, rfl, hchain, a, b, hhead, hlast, hclose⟩private theorem in833_core_out_unique (α : Type) [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (T S : Finset α) (hST : S ⊆ T) (hloop : ∀ v, ¬ D.Adj v v) (hstrong : ∀ u ∈ T, ∀ v ∈ T, ∃ p : List α, digraph_is_directed_path D p u v ∧ ∀ z ∈ p, z ∈ T) (hcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on D C → S ⊆ C) : ∀ x ∈ T, (S.filter fun y => D.Adj x y).card ≤ 1 := by classical intro x hx apply Finset.card_le_one.mpr intro a ha b hb have haS : a ∈ S := (Finset.mem_filter.mp ha).1 have hbS : b ∈ S := (Finset.mem_filter.mp hb).1 have hxa : D.Adj x a := (Finset.mem_filter.mp ha).2 have hxb : D.Adj x b := (Finset.mem_filter.mp hb).2 by_contra hab have hax : a ≠ x := by intro h; subst a; exact (hloop x) hxa have hbx : b ≠ x := by intro h; subst b; exact (hloop x) hxb obtain ⟨p,hpath,hpT⟩ := hstrong a (hST haS) x hx obtain ⟨hchain, hnodup, hhead, hlast⟩ := hpath by_cases hbp : b ∈ p · obtain ⟨pre,tail,hp⟩ := List.mem_iff_append.mp hbp cases pre with | nil => simp only [List.nil_append, List.head?_cons, Option.some.injEq] at hp hhead have : a = b := by simpa [hp] using hhead.symm exact hab this | cons z zs => have hz : z = a := by rw [hp] at hhead simpa using hhead subst z have hnodup' : ((a :: zs) ++ b :: tail).Nodup := by simpa [hp] using hnodup have hsufnodup : (b :: tail).Nodup := (List.nodup_append.mp hnodup').2.1 have hnot : a ∉ b :: tail := by intro ha' exact (List.nodup_append.mp hnodup').2.2 a (by simp) a ha' rfl have hchain' : ((a :: zs) ++ b :: tail).IsChain D.Adj := by simpa [hp] using hchain have hsufchain : (b :: tail).IsChain D.Adj := hchain'.right_of_append have hsuflast : (b :: tail).getLast? = some x := by rw [hp, List.getLast?_append_cons] at hlast exact hlast have hsufpath : digraph_is_directed_path D (b :: tail) b x := ⟨hsufchain, hsufnodup, by simp, hsuflast⟩ have hcycle := in833_path_close_cycle D (b :: tail) b x hsufpath hbx hxb have hsub : (b :: tail).toFinset ⊆ T := by intro y hy have hy' : y ∈ b :: tail := by simpa using hy apply hpT y rw [hp] exact List.mem_append_right _ hy' have hc := hcore (b :: tail).toFinset hsub hcycle haS exact hnot (by simpa using hc) · have hcycle := in833_path_close_cycle D p a x ⟨hchain,hnodup,hhead,hlast⟩ hax hxa have hsub : p.toFinset ⊆ T := by intro y hy apply hpT y simpa using hy have hc := hcore p.toFinset hsub hcycle hbS exact hbp (by simpa using hc)private theorem in833_core_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_common_cycle_core_neighbor_unique (α : Type) [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (T S : Finset α) (hST : S ⊆ T) (hloop : ∀ v, ¬ D.Adj v v) (hstrong : ∀ u ∈ T, ∀ v ∈ T, ∃ p : List α, digraph_is_directed_path D p u v ∧ ∀ z ∈ p, z ∈ T) (hcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on D C → S ⊆ C) : ∀ x ∈ T, (S.filter fun y => D.Adj x y).card ≤ 1 ∧ (S.filter fun y => D.Adj y x).card ≤ 1 := by classical have hout := in833_core_out_unique α D T S hST hloop hstrong hcore let E : Digraph α := ⟨fun u v => D.Adj v u⟩ have hEloop : ∀ v, ¬ E.Adj v v := hloop have hEstrong : ∀ u ∈ T, ∀ v ∈ T, ∃ p : List α, digraph_is_directed_path E p u v ∧ ∀ z ∈ p, z ∈ T := by intro u hu v hv obtain ⟨p,hp,hT⟩ := hstrong v hv u hu obtain ⟨hc,hn,hh,hl⟩ := hp refine ⟨p.reverse, ?_, ?_⟩ · refine ⟨?_, by simpa using hn, ?_, ?_⟩ · exact List.isChain_reverse.mpr hc · simpa using hl · simpa using hh · intro z hz apply hT z simpa using hz have hEcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on E C → S ⊆ C := by intro C hsub hc exact hcore C hsub (in833_core_reverse_cycle D C hc) have hin := in833_core_out_unique α E T S hST hEloop hEstrong hEcore intro x hx refine ⟨hout x hx, ?_⟩ simpa [E] using hin x hx