digraph_common_cycle_core_excludes_high_degree_vertices
Suppose a finite vertex set T is covered by R and P, P has at most k minus two vertices, every directed cycle in T contains a nonempty set S, every vertex of T has at most one outneighbor in S, and every vertex of T in R outside S has at least k outneighbors in T. Then T is disjoint from R outside S.
Statement
theorem digraph_common_cycle_core_excludes_high_degree_vertices (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (T R S P : Finset α) (k : ℕ) (hloop : ∀ x, ¬ D.Adj x x) (hne : S.Nonempty) (hcover : T ⊆ R ∪ P) (hP : P.card + 2 ≤ k) (hcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on D C → S ⊆ C) (huniq : ∀ x ∈ T, (S.filter fun y => D.Adj x y).card ≤ 1) (hdeg : ∀ x ∈ T, x ∈ R → x ∉ S → k ≤ (T.filter fun y => D.Adj x y).card) : Disjoint T (R \ S)
- Source
- Common-cycle core counting for the oriented twenty-cut profile.
- 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_low_cut_contains_cycleIn a finite loopless digraph with minimum outdegree at least r, a vertex set of at least r vertices contains a directed cycle if fewer…
- Used by 2
- 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.
The proof, explained
To show that T and R \ S are disjoint, the proof considers their intersection X = T ∩ (R \ S) and shows it is empty by contradiction. If X were nonempty, counting outneighbors shows that every vertex in X has at least one outneighbor inside X, because its outdegree in T is at least k, while S absorbs at most 1 outneighbor and P contains at most k - 2 vertices. In a finite loopless digraph, such a subset must contain a directed cycle C ⊆ X ⊆ T. However, by hypothesis every cycle in T contains the nonempty set S, which forces S ⊆ X and directly contradicts the fact that X contains no elements of S.
Define the candidate intersection set X = T ∩ (R \ S).
We enable classical reasoning and introduce X as the set of vertices in T that belong to R but not to S. Disjointness of T and R \ S is equivalent to showing that X is empty.
classical let X := T ∩ (R \ S)Every vertex in X has at least one outneighbor in X.
Fix x ∈ X; then x ∈ T, x ∈ R, and x ∉ S. Let I, A, and B be the sets of outneighbors of x in T, X, and S, respectively. Since T ⊆ R ∪ P, every outneighbor y ∈ I lies in S (so y ∈ B), in P, or in R \ S (which places y in X = T ∩ (R \ S) since y ∈ T, so y ∈ A). Hence I ⊆ (A ∪ B) ∪ P. By subadditivity of cardinalities, |I| ≤ |A| + |B| + |P|. But x ∈ R \ S has outdegree at least k in T (|I| ≥ k), at most 1 outneighbor in S (|B| ≤ 1), and |P| ≤ k - 2. Linear arithmetic (omega) then forces |A| ≥ |I| - |B| - |P| ≥ k - 1 - (k - 2) = 1.
uses
Finset.mem_inter.mp,Finset.mem_sdiff.mp,Finset.mem_filter.mp,Finset.mem_union_left,Finset.mem_union_right,Finset.mem_filter.mpr,Finset.mem_union.mp,Finset.mem_inter.mpr,Finset.mem_sdiff.mpr,Finset.card_le_card,Finset.card_union_lehave hout : ∀ x ∈ X, 1 ≤ (X.filter fun y => D.Adj x y).card := by intro x hx have hxT : x ∈ T := (Finset.mem_inter.mp hx).1 have hxR : x ∈ R := (Finset.mem_sdiff.mp (Finset.mem_inter.mp hx).2).1 have hxS : x ∉ S := (Finset.mem_sdiff.mp (Finset.mem_inter.mp hx).2).2 let I := T.filter fun y => D.Adj x y let A := X.filter fun y => D.Adj x y let B := S.filter fun y => D.Adj x y have hsub : I ⊆ (A ∪ B) ∪ P := by intro y hy have hyT := (Finset.mem_filter.mp hy).1 have hyD := (Finset.mem_filter.mp hy).2 have hyRP := hcover hyT by_cases hyS : y ∈ S · apply Finset.mem_union_left apply Finset.mem_union_right exact Finset.mem_filter.mpr ⟨hyS,hyD⟩ · rcases Finset.mem_union.mp hyRP with hyR | hyP · apply Finset.mem_union_left apply Finset.mem_union_left exact Finset.mem_filter.mpr ⟨Finset.mem_inter.mpr ⟨hyT,Finset.mem_sdiff.mpr ⟨hyR,hyS⟩⟩,hyD⟩ · exact Finset.mem_union_right _ hyP have h1 := Finset.card_le_card hsub have h2 := Finset.card_union_le (A ∪ B) P have h3 := Finset.card_union_le A B have h4 : B.card ≤ 1 := huniq x hxT have h5 : k ≤ I.card := hdeg x hxT hxR hxS change 1 ≤ A.card omega
The set X is empty.
Suppose for contradiction that X is nonempty. Since every vertex in X has an outneighbor in X, the graph has no self-loops, and α is finite, the lemma digraph_low_cut_contains_cycle_outdeg_cycle provides a directed cycle C entirely contained in X. Because X ⊆ T, C is a directed cycle in T, so by assumption hcore, the set S must be a subset of C. Since S is nonempty, choosing any s ∈ S yields s ∈ C ⊆ X. But every element of X lies outside S by definition of X = T ∩ (R \ S), giving s ∉ S, which is a contradiction.
uses
Finset.nonempty_iff_ne_empty.mpr,Finset.card_pos.mp,Finset.mem_filter.mp,digraph_low_cut_contains_cycle_outdeg_cycle,Finset.mem_inter.mp,Finset.mem_sdiff.mphave hX : X = ∅ := by by_contra hh have hXne : X.Nonempty := Finset.nonempty_iff_ne_empty.mpr hh have hsuccessor : ∀ x ∈ X, ∃ y ∈ X, D.Adj x y := by intro x hx obtain ⟨y,hy⟩ := Finset.card_pos.mp (by have := hout x hx; omega : 0 < (X.filter fun y => D.Adj x y).card) exact ⟨y,(Finset.mem_filter.mp hy).1,(Finset.mem_filter.mp hy).2⟩ obtain ⟨C,hCX,hcyc⟩ := digraph_low_cut_contains_cycle_outdeg_cycle α D hloop X hXne hsuccessor have hCT : C ⊆ T := by intro x hx exact (Finset.mem_inter.mp (hCX hx)).1 have hSC := hcore C hCT hcyc obtain ⟨s,hs⟩ := hne have hsX := hCX (hSC hs) exact (Finset.mem_sdiff.mp (Finset.mem_inter.mp hsX).2).2 hs
T and R \ S are disjoint.
Any element in both T and R \ S would lie in their intersection X. Since X = ∅, no such element exists, proving that T and R \ S are disjoint.
uses
Finset.disjoint_left.mpr,Finset.mem_inter.mprapply Finset.disjoint_left.mpr intro x hxT hxRS have hx : x ∈ X := Finset.mem_inter.mpr ⟨hxT,hxRS⟩ rw [hX] at hx simpa using hx
digraph_low_cut_contains_cycle_outdeg_cycle- In a finite loopless directed graph, if a nonempty subset of vertices has every vertex possessing an outneighbor in the subset, then the subset contains a directed cycle.
Finset.card_le_card- A finite subset has cardinality at most that of its superset.
Finset.card_pos.mp- A finite set with strictly positive cardinality is nonempty.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their individual cardinalities.
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first belongs to the second.
Finset.mem_filter.mp- An element of a filtered set belongs to the original set and satisfies the filtering condition.
Finset.mem_filter.mpr- An element that belongs to a set and satisfies a predicate belongs to the filtered set.
Finset.mem_inter.mp- An element of an intersection belongs to both sets.
Finset.mem_inter.mpr- An element belonging to both sets belongs to their intersection.
Finset.mem_sdiff.mp- An element of a set difference belongs to the first set and not to the second.
Finset.mem_sdiff.mpr- An element that belongs to the first set and not the second belongs to their set difference.
Finset.mem_union.mp- An element of a union belongs to at least one of the sets.
Finset.mem_union_left- An element belonging to the first set of a union belongs to the union.
Finset.mem_union_right- An element belonging to the second set of a union belongs to the union.
Finset.nonempty_iff_ne_empty.mpr- A set that is not equal to the empty set is nonempty.
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 4096theorem digraph_common_cycle_core_excludes_high_degree_vertices (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (T R S P : Finset α) (k : ℕ) (hloop : ∀ x, ¬ D.Adj x x) (hne : S.Nonempty) (hcover : T ⊆ R ∪ P) (hP : P.card + 2 ≤ k) (hcore : ∀ C : Finset α, C ⊆ T → digraph_directed_cycle_on D C → S ⊆ C) (huniq : ∀ x ∈ T, (S.filter fun y => D.Adj x y).card ≤ 1) (hdeg : ∀ x ∈ T, x ∈ R → x ∉ S → k ≤ (T.filter fun y => D.Adj x y).card) : Disjoint T (R \ S) := by classical let X := T ∩ (R \ S) have hout : ∀ x ∈ X, 1 ≤ (X.filter fun y => D.Adj x y).card := by intro x hx have hxT : x ∈ T := (Finset.mem_inter.mp hx).1 have hxR : x ∈ R := (Finset.mem_sdiff.mp (Finset.mem_inter.mp hx).2).1 have hxS : x ∉ S := (Finset.mem_sdiff.mp (Finset.mem_inter.mp hx).2).2 let I := T.filter fun y => D.Adj x y let A := X.filter fun y => D.Adj x y let B := S.filter fun y => D.Adj x y have hsub : I ⊆ (A ∪ B) ∪ P := by intro y hy have hyT := (Finset.mem_filter.mp hy).1 have hyD := (Finset.mem_filter.mp hy).2 have hyRP := hcover hyT by_cases hyS : y ∈ S · apply Finset.mem_union_left apply Finset.mem_union_right exact Finset.mem_filter.mpr ⟨hyS,hyD⟩ · rcases Finset.mem_union.mp hyRP with hyR | hyP · apply Finset.mem_union_left apply Finset.mem_union_left exact Finset.mem_filter.mpr ⟨Finset.mem_inter.mpr ⟨hyT,Finset.mem_sdiff.mpr ⟨hyR,hyS⟩⟩,hyD⟩ · exact Finset.mem_union_right _ hyP have h1 := Finset.card_le_card hsub have h2 := Finset.card_union_le (A ∪ B) P have h3 := Finset.card_union_le A B have h4 : B.card ≤ 1 := huniq x hxT have h5 : k ≤ I.card := hdeg x hxT hxR hxS change 1 ≤ A.card omega have hX : X = ∅ := by by_contra hh have hXne : X.Nonempty := Finset.nonempty_iff_ne_empty.mpr hh have hsuccessor : ∀ x ∈ X, ∃ y ∈ X, D.Adj x y := by intro x hx obtain ⟨y,hy⟩ := Finset.card_pos.mp (by have := hout x hx; omega : 0 < (X.filter fun y => D.Adj x y).card) exact ⟨y,(Finset.mem_filter.mp hy).1,(Finset.mem_filter.mp hy).2⟩ obtain ⟨C,hCX,hcyc⟩ := digraph_low_cut_contains_cycle_outdeg_cycle α D hloop X hXne hsuccessor have hCT : C ⊆ T := by intro x hx exact (Finset.mem_inter.mp (hCX hx)).1 have hSC := hcore C hCT hcyc obtain ⟨s,hs⟩ := hne have hsX := hCX (hSC hs) exact (Finset.mem_sdiff.mp (Finset.mem_inter.mp hsX).2).2 hs apply Finset.disjoint_left.mpr intro x hxT hxRS have hx : x ∈ X := Finset.mem_inter.mpr ⟨hxT,hxRS⟩ rw [hX] at hx simpa using hx