digraph_low_cut_contains_cycle
In a finite loopless digraph with minimum outdegree at least r, a vertex set of at least r vertices contains a directed cycle if fewer than r(r+1)/2 arcs leave it.
Statement
theorem digraph_low_cut_contains_cycle (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (r : ℕ) (hloop : ∀ v, ¬ D.Adj v v) (hdeg : ∀ v, r ≤ (Finset.univ.filter fun w => D.Adj v w).card) (B : Finset α) (hB : r ≤ B.card) (hcut : (∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card) < r * (r + 1) / 2) : ∃ C : Finset α, C ⊆ B ∧ digraph_directed_cycle_on D C
- Source
- Cut-count reduction for the minimum-counterexample route to OP-110.
- Verified
- 03 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…
- Used by 4
- digraph_17_shared_target_forces_two_cyclesThe normalized oriented seventeen-vertex shared-target configuration with three designated parents contains two disjoint cycles, assuming…
- digraph_common_cycle_core_excludes_high_degree_verticesSuppose 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…
- 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_16_shared_target_many_low_arcsIn the displayed oriented sixteen-vertex configuration with no two disjoint cycles, at least four outneighbors of the common target point…
The proof, explained
The theorem is proved by contradiction: assuming a vertex set $B$ of size at least $r$ contains no directed cycle, we can iteratively peel $r$ distinct vertices $s(0), \dots, s(r-1)$ from $B$ such that each $s(j)$ has at most $j$ out-neighbours inside $B$. Because every vertex in the digraph has total out-degree at least $r$, each peeled vertex $s(j)$ must send at least $r - j$ arcs into the complement $B^c$. Summing these outgoing arcs over all $j \in \{0, \dots, r-1\}$ yields at least $\sum_{j=0}^{r-1}(r - j) = r(r+1)/2$ arcs leaving $B$, contradicting the cut assumption that fewer than $r(r+1)/2$ arcs leave $B$.
The sum $\sum_{j \in \mathrm{Fin}\, r} (r - j)$ is rewritten as $\sum_{k=0}^{r-1} (k + 1)$.
We first convert the sum over `Fin r` to a sum over the range $\{0, \dots, r-1\}$ using `Finset.sum_fin_eq_sum_range`. Then we reflect the sum using `Finset.sum_range_reflect`, substituting $r - 1 - k$ for $k$, which transforms the summand $r - k$ into $(k + 1)$ via linear arithmetic (`omega`).
uses
Finset.sum_fin_eq_sum_range,Finset.sum_congr,Finset.mem_range,Finset.sum_range_reflecthave h1 : (∑ j : Fin r, (r - (j:ℕ))) = ∑ k ∈ Finset.range r, (r - k) := by rw [Finset.sum_fin_eq_sum_range] refine Finset.sum_congr rfl ?_ intro k hk simp only [Finset.mem_range] at hk simp [hk] rw [h1] have h2 : ∑ k ∈ Finset.range r, (r - k) = ∑ k ∈ Finset.range r, (k + 1) := by have := Finset.sum_range_reflect (fun k => k + 1) r rw [← this] refine Finset.sum_congr rfl ?_ intro k hk simp only [Finset.mem_range] at hk omega rw [h2]
The sum formula $\sum_{j \in \mathrm{Fin}\, r} (r - j) = r(r + 1)/2$ is established.
We split $\sum_{k=0}^{r-1} (k + 1)$ into $\sum_{k=0}^{r-1} k + \sum_{k=0}^{r-1} 1$ using `Finset.sum_add_distrib`. The constant sum evaluates to $r$, and the identity sum evaluates to $r(r - 1)/2$ by `Finset.sum_range_id`. Multiplying both sides by 2 and simplifying using the identity $r(r - 1) + 2r = r(r + 1)$ completes the proof of `digraph_low_cut_contains_cycle_sum_fin`.
uses
Finset.sum_add_distrib,Finset.sum_const_nat,Finset.card_range,mul_one,Finset.sum_range_id,Nat.eq_div_of_mul_eq_right,Nat.mul_comm,Nat.div_two_mul_two_of_even,Nat.even_mul_pred_self,Nat.mul_addrw [Finset.sum_add_distrib] simp only [Finset.sum_const_nat (m := 1) (fun x _ => rfl), Finset.card_range, mul_one] rw [Finset.sum_range_id] apply Nat.eq_div_of_mul_eq_right (c := 2) (by norm_num) have h2even : r * (r - 1) = 2 * (r * (r - 1) / 2) := by rw [Nat.mul_comm 2, Nat.div_two_mul_two_of_even (Nat.even_mul_pred_self r)] have key : r * (r - 1) + 2 * r = r * (r + 1) := by cases r with | zero => simp | succ n => have hsub : n + 1 - 1 = n := by omega rw [hsub] ring rw [Nat.mul_add, ← h2even] exact key
An out-neighbour step function $\mathrm{step} : S \to S$ and a sequence of iterates $x(t) = \mathrm{step}^t(s_0)$ are defined on the subtype $S = X$, with $x(t) \to x(t+1)$ for all $t$.
Since every vertex in $X$ has an out-neighbour in $X$, we use the axiom of choice to define a transition function $\mathrm{step} : S \to S$ such that $s \to \mathrm{step}(s)$. Starting from an arbitrary vertex $s_0 = v_0 \in X$, iterating $\mathrm{step}$ produces a sequence $x : \mathbb{N} \to S$ where consecutive vertices are adjacent by `Function.iterate_succ_apply'`.
uses
Function.iterate_succ_apply'let S := {x : α // x ∈ X} have hS : ∀ s : S, ∃ t : S, D.Adj s.1 t.1 := by intro s; obtain ⟨w, hw, hadj⟩ := hout s.1 s.2; exact ⟨⟨w, hw⟩, hadj⟩ let step : S → S := fun s => (hS s).choose have hstep : ∀ s : S, D.Adj s.1 (step s).1 := fun s => (hS s).choose_spec obtain ⟨v0, hv0⟩ := hne let s0 : S := ⟨v0, hv0⟩ 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 (x (t + 1)).1 := by intro t; rw [hxstep]; exact hstep (x t)
There exist indices $m < n$ such that $x(m) = x(n)$.
Since the sequence domain $\mathbb{N}$ is infinite and the codomain $S = X$ is finite, the sequence $x$ cannot be injective by `not_injective_infinite_finite`. By trichotomy on indices (`lt_trichotomy`), non-injectivity guarantees a pair of distinct indices $m < n$ with $x(m) = x(n)$.
uses
not_injective_infinite_finite,lt_trichotomyhave 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
Taking $n$ minimal with a preceding duplicate $m < n$, all vertices prior to $n$ are distinct and the cycle length $n - m$ is at least 2.
We choose $n$ to be the least index having an earlier duplicate $m < n$ using `Nat.find`. The minimality from `Nat.find_min` implies that all indices strictly before $n$ map to distinct vertices (`hinj`). If $n - m = 1$, then $x(m) \to x(m+1) = x(m)$ would be a self-loop, contradicting `hloop`. Thus $n - m \ge 2$.
uses
Nat.find_spec,Nat.find_min,lt_trichotomyclassical 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 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
The vertex list $l = [x(m), x(m+1), \dots, x(n-1)]$ has length $k = n - m \ge 2$ and contains no duplicate vertices.
We define $l$ as the image of $[0, \dots, k-1]$ under $i \mapsto x(m + i)$. Because each $m + i < n$, the injectivity of $x$ on $\{0, \dots, n-1\}$ implies that the map is injective on the range, so $l$ has no duplicates by `List.nodup_map_iff_inj_on` and `List.nodup_range`.
uses
List.nodup_map_iff_inj_on,List.nodup_range,List.mem_range,Subtype.extlet k := n - m let c : ℕ → α := fun i => (x (m + 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 (m + i) = x (m + j) := Subtype.ext hij have hi' : m + i < n := by omega have hj' : m + j < n := by omega have : m + i = m + j := hinj (m + i) hi' (m + j) hj' heq omega
The list $l$ forms a directed chain and its last vertex is adjacent to its first vertex, closing a cycle.
By `List.isChain_iff_getElem`, consecutive elements $l[i] = x(m+i)$ and $l[i+1] = x(m+i+1)$ are adjacent because $x(t) \to x(t+1)$. Furthermore, the last vertex $l[k-1] = x(n-1)$ is adjacent to $x(n) = x(m) = l[0]$, closing the directed cycle.
uses
List.isChain_iff_getElem,List.head?_map,List.head?_range,List.getLast?_map,List.getLast?_rangehave 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 : m + (i + 1) = (m + i) + 1 := by omega rw [hrel]; exact hxadj (m + i) have hhead : l.head? = some (c 0) := by rw [List.head?_map, List.head?_range] have hk0 : k ≠ 0 := by omega simp [hk0] have hlast : l.getLast? = some (c (k - 1)) := by rw [List.getLast?_map, List.getLast?_range] have hk0 : k ≠ 0 := by omega simp [hk0] have hadj_last_head : D.Adj (c (k - 1)) (c 0) := by have h1 : m + (k - 1) = n - 1 := by omega have h2 : m + 0 = m := by omega show D.Adj (x (m + (k - 1))).1 (x (m + 0)).1 rw [h1, h2, hxmn] have hn : (n - 1) + 1 = n := by omega show D.Adj (x (n - 1)).1 (x n).1 rw [← hn]; exact hxadj (n - 1)
The vertex set of $l$ is a subset of $X$ and forms a directed cycle on $D$, completing `digraph_low_cut_contains_cycle_outdeg_cycle`.
The cycle condition `digraph_directed_cycle_on D (l.toFinset)` is satisfied by the nodup chain $l$ of length $k \ge 2$ with last-to-first adjacency. Every vertex in $l$ comes from the subtype $S = X$, so $l.\mathrm{toFinset} \subseteq X$.
uses
List.mem_toFinset,List.mem_maprefine ⟨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 (m + i)).2
Every finite nonempty cycle-free vertex set contains a sink vertex with no out-neighbours in the set (`digraph_low_cut_contains_cycle_sink`).
By contradiction: if every vertex in $X$ had an out-neighbour in $X$, then `digraph_low_cut_contains_cycle_outdeg_cycle` would produce a directed cycle contained in $X$, contradicting the assumption that $X$ contains no directed cycle.
uses
digraph_low_cut_contains_cycle_outdeg_cycleby_contra h push Not at h obtain ⟨C, hCX, hcyc⟩ := digraph_low_cut_contains_cycle_outdeg_cycle α D hloop X hne h exact hac C hCX hcyc
The base case $r = 0$ of the vertex peeling lemma holds vacuously.
When $r = 0$, the empty function `Fin.elim0` on `Fin 0` vacuously satisfies injectivity, membership in $X$, and the degree bound.
uses
Fin.elim0intro r induction r with | zero => intro X hac hr exact ⟨Fin.elim0, fun i => i.elim0, fun i => i.elim0, fun i => i.elim0⟩
For $r + 1$, a sink $s_0 \in X$ is peeled, induction provides $r$ vertices $s'$ from $X \setminus \{s_0\}$, and prepending $s_0$ gives an injective sequence $s$.
Since $|X| \ge r + 1 > 0$, $X$ is nonempty by `Finset.card_pos`. By `digraph_low_cut_contains_cycle_sink`, $X$ contains a sink $s_0$ with no out-neighbours in $X$. The set $X \setminus \{s_0\}$ remains acyclic and has size at least $r$ by `Finset.card_erase_of_mem`. The induction hypothesis yields an injective map $s' : \mathrm{Fin}\, r \to X \setminus \{s_0\}$. Since $s_0 \notin X \setminus \{s_0\}$, prepending $s_0$ via `Fin.cons` yields an injective map $s : \mathrm{Fin}(r+1) \to \alpha$ by `Fin.cons_injective_of_injective`.
uses
Finset.card_pos,digraph_low_cut_contains_cycle_sink,Finset.erase_subset,Finset.card_erase_of_mem,Fin.cons_injective_of_injective,Finset.mem_erase| succ r ih => intro X hac hr have hne : X.Nonempty := Finset.card_pos.mp (by omega) obtain ⟨s0, hs0X, hsink⟩ := digraph_low_cut_contains_cycle_sink α D hloop X hne hac have hac' : ∀ C, C ⊆ X.erase s0 → ¬ digraph_directed_cycle_on D C := fun C hC => hac C (hC.trans (Finset.erase_subset s0 X)) have hr' : r ≤ (X.erase s0).card := by rw [Finset.card_erase_of_mem hs0X]; omega obtain ⟨s', hinj', hmem', hbound'⟩ := ih (X.erase s0) hac' hr' let s : Fin (r+1) → α := Fin.cons s0 s' refine ⟨s, ?_, ?_, ?_⟩ · show Function.Injective (Fin.cons s0 s') apply Fin.cons_injective_of_injective · rintro ⟨i, hi⟩ exact (Finset.mem_erase.mp (hmem' i)).1 hi · exact hinj'Every peeled vertex in the extended sequence $s$ belongs to $X$.
By case analysis on `Fin(r+1)` using `Fin.cases`: the initial vertex $s(0) = s_0$ belongs to $X$ by definition of the sink, while for any successor $i+1$, $s(i+1) = s'(i) \in X \setminus \{s_0\} \subseteq X$.
uses
Fin.cases,Fin.cons_zero,Fin.cons_succ,Finset.mem_erase· intro j induction j using Fin.cases with | zero => simpa only [s, Fin.cons_zero] using hs0X | succ i => simpa only [s, Fin.cons_succ] using (Finset.mem_erase.mp (hmem' i)).2
The $j$-th peeled vertex has at most $j$ out-neighbours in $X$, completing the proof of `digraph_low_cut_contains_cycle_peel`.
For $j = 0$, $s(0) = s_0$ is a sink in $X$, so it has 0 out-neighbours in $X$, satisfying the bound $0 \le 0$. For $j = i+1$, $s(i+1) = s'(i)$ has out-neighbours inside $X \subseteq (X \setminus \{s_0\}) \cup \{s_0\}$. By the induction hypothesis, it has at most $i$ out-neighbours in $X \setminus \{s_0\}$. Adding the singleton $\{s_0\}$ gives at most $i + 1 = j$ out-neighbours in $X$ via `Finset.card_union_le` and `omega`.
uses
Fin.cases,Fin.cons_zero,Finset.filter_eq_empty_iff,Fin.cons_succ,Finset.mem_filter,Finset.mem_union,Finset.mem_erase,Finset.card_le_card,Finset.card_union_le,Finset.card_singleton,Fin.val_succ· intro j induction j using Fin.cases with | zero => have hempty : X.filter (fun w => D.Adj (s 0) w) = ∅ := by simp only [s, Fin.cons_zero] rw [Finset.filter_eq_empty_iff] intro w hw exact hsink w hw rw [hempty] simp | succ i => simp only [s, Fin.cons_succ] have hsub : X.filter (fun w => D.Adj (s' i) w) ⊆ (X.erase s0).filter (fun w => D.Adj (s' i) w) ∪ ({s0} : Finset α) := by intro w hw simp only [Finset.mem_filter] at hw rw [Finset.mem_union] by_cases hw0 : w = s0 · right; simp [hw0] · left simp only [Finset.mem_filter, Finset.mem_erase] exact ⟨⟨hw0, hw.1⟩, hw.2⟩ have h1 := Finset.card_le_card hsub have h2 := Finset.card_union_le ((X.erase s0).filter (fun w => D.Adj (s' i) w)) ({s0} : Finset α) have h3 := hbound' i rw [Finset.card_singleton] at h2 simp only [Fin.val_succ] omega
Assuming $B$ contains no directed cycle, we peel $r$ distinct vertices $s(0), \dots, s(r-1) \in B$ with at most $j$ internal out-neighbours each.
We proceed by contradiction, assuming $B$ contains no directed cycle. Applying `digraph_low_cut_contains_cycle_peel` to $B$ (which has $|B| \ge r$) yields an injective sequence $s : \mathrm{Fin}\, r \to B$ where each $s(j)$ has at most $j$ out-neighbours inside $B$.
uses
digraph_low_cut_contains_cycle_peelby_contra hno push Not at hno obtain ⟨s, hinj, hmem, hbound⟩ := digraph_low_cut_contains_cycle_peel α D hloop r B hno hB
Each peeled vertex $s(j)$ sends at least $r - j$ directed edges into $B^c$.
The total out-neighbourhood of $s(j)$ is partitioned into disjoint sets of neighbours inside $B$ and in $B^c$ using `Finset.card_union_of_disjoint`. Since the total out-degree is at least $r$ and the internal out-degree is at most $j$, linear arithmetic (`omega`) gives at least $r - j$ neighbours in $B^c$.
uses
Finset.disjoint_left,Finset.mem_filter,Finset.mem_compl,Finset.filter_union,Finset.union_compl,Finset.card_union_of_disjointhave hterm : ∀ j : Fin r, r - (j:ℕ) ≤ (Bᶜ.filter fun w => D.Adj (s j) w).card := by intro j have hout : r ≤ (Finset.univ.filter (fun w => D.Adj (s j) w)).card := hdeg (s j) have hint : (B.filter (fun w => D.Adj (s j) w)).card ≤ (j:ℕ) := hbound j have hdisj : Disjoint (B.filter (fun w => D.Adj (s j) w)) (Bᶜ.filter (fun w => D.Adj (s j) w)) := by rw [Finset.disjoint_left] intro x hx hx' simp only [Finset.mem_filter] at hx hx' exact (Finset.mem_compl.mp hx'.1) hx.1 have hunion : B.filter (fun w => D.Adj (s j) w) ∪ Bᶜ.filter (fun w => D.Adj (s j) w) = Finset.univ.filter (fun w => D.Adj (s j) w) := by rw [← Finset.filter_union, Finset.union_compl] have hpart : (Finset.univ.filter (fun w => D.Adj (s j) w)).card = (B.filter (fun w => D.Adj (s j) w)).card + (Bᶜ.filter (fun w => D.Adj (s j) w)).card := by rw [← hunion, Finset.card_union_of_disjoint hdisj] omega
The total number of arcs leaving the peeled vertices into $B^c$ is at least $r(r+1)/2$.
Summing the individual lower bounds $r - j$ over all $j \in \mathrm{Fin}\, r$ via `Finset.sum_le_sum` and applying the identity $\sum_{j \in \mathrm{Fin}\, r} (r - j) = r(r+1)/2$ from `digraph_low_cut_contains_cycle_sum_fin` gives a lower bound of $r(r+1)/2$.
uses
Finset.sum_le_sum,digraph_low_cut_contains_cycle_sum_finhave hsum_ge : r * (r + 1) / 2 ≤ ∑ j : Fin r, (Bᶜ.filter fun w => D.Adj (s j) w).card := by have h1 : ∑ j : Fin r, (r - (j:ℕ)) ≤ ∑ j : Fin r, (Bᶜ.filter fun w => D.Adj (s j) w).card := Finset.sum_le_sum (fun j _ => hterm j) rwa [digraph_low_cut_contains_cycle_sum_fin r] at h1
The sum of arcs leaving the peeled vertices is bounded by the total cut size leaving $B$.
Because $s$ is injective, the sum over $j \in \mathrm{Fin}\, r$ equals the sum over the image $s(\mathrm{Fin}\, r) \subseteq B$ by `Finset.sum_image`. Since all terms are non-negative, `Finset.sum_le_sum_of_subset_of_nonneg` bounds this by the total sum over all vertices in $B$.
uses
Finset.sum_image,Finset.sum_le_sum_of_subset_of_nonneg,Finset.image_subset_iff,Nat.zero_lehave hsum_le : ∑ j : Fin r, (Bᶜ.filter fun w => D.Adj (s j) w).card ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card := by have himg : ∑ j : Fin r, (Bᶜ.filter fun w => D.Adj (s j) w).card = ∑ v ∈ (Finset.univ.image s), (Bᶜ.filter fun w => D.Adj v w).card := by rw [Finset.sum_image (f := fun v => (Bᶜ.filter fun w => D.Adj v w).card) (g := s) (s := Finset.univ) (fun i _ j _ h => hinj h)] rw [himg] exact Finset.sum_le_sum_of_subset_of_nonneg (Finset.image_subset_iff.mpr (fun j _ => hmem j)) (fun v _ _ => Nat.zero_le _)
At least $r(r+1)/2$ arcs leave $B$, which contradicts the cut hypothesis and completes the proof.
Combining the lower bound $r(r+1)/2 \le \sum_{j} \mathrm{outdeg}(s(j), B^c)$ and the upper bound $\sum_{j} \mathrm{outdeg}(s(j), B^c) \le \sum_{v \in B} \mathrm{outdeg}(v, B^c)$ by transitivity (`le_trans`) yields $r(r+1)/2 \le \sum_{v \in B} \mathrm{outdeg}(v, B^c)$. This directly contradicts the hypothesis that the cut size is strictly less than $r(r+1)/2$, completing the contradiction via `absurd` and `not_lt`.
uses
le_trans,absurd,not_lthave hfinal : r * (r + 1) / 2 ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card := le_trans hsum_ge hsum_le exact absurd hcut (not_lt.mpr hfinal)
Finset.sum_fin_eq_sum_range- A sum over `Fin n` is equal to the sum of the same terms over the range $\{0, \dots, n-1\}$.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element.
Finset.mem_range- An element $k$ belongs to $\mathrm{range}(n)$ if and only if $k < n$.
Finset.sum_range_reflect- Reversing the index order in a sum over a range preserves the sum: $\sum_{j < n} f(n - 1 - j) = \sum_{j < n} f(j)$.
Finset.sum_add_distrib- The sum of a sum of functions equals the sum of the individual sums: $\sum (f(x) + g(x)) = \sum f(x) + \sum g(x)$.
Finset.sum_const_nat- Summing a constant value $m$ over a finite set $s$ yields $|s| \cdot m$.
Finset.card_range- The cardinality of the range $\{0, \dots, n-1\}$ is $n$.
mul_one- Multiplying by 1 preserves any element: $a \cdot 1 = a$.
Finset.sum_range_id- The sum of identity integers $\sum_{i=0}^{n-1} i$ equals $n(n - 1)/2$.
Nat.eq_div_of_mul_eq_right- If $c \neq 0$ and $c \cdot a = b$, then $a = b / c$.
Nat.mul_comm- Multiplication of natural numbers is commutative: $n \cdot m = m \cdot n$.
Nat.div_two_mul_two_of_even- If $n$ is an even natural number, then $(n / 2) \cdot 2 = n$.
Nat.even_mul_pred_self- The product of a natural number and its predecessor $n(n - 1)$ is always even.
Nat.mul_add- Multiplication distributes over addition for natural numbers: $n(m + k) = nm + nk$.
Function.iterate_succ_apply'- The $(n+1)$-th iterate of $f$ on $x$ satisfies $f^{n+1}(x) = f(f^n(x))$.
not_injective_infinite_finite- No function from an infinite set to a finite set is injective (pigeonhole principle).
lt_trichotomy- For any two elements in a linear order, exactly one of $a < b$, $a = b$, or $b < a$ holds.
Nat.find_spec- The index found by `Nat.find` satisfies the existential property.
Nat.find_min- Any natural number strictly smaller than `Nat.find` does not satisfy the property.
List.nodup_map_iff_inj_on- For a list with no duplicates, mapping by $f$ yields a list with no duplicates if and only if $f$ is injective on the elements of the list.
List.nodup_range- The range list $[0, \dots, n-1]$ contains no duplicate elements.
Subtype.ext- Two elements of a subtype are equal if and only if their underlying values are equal.
List.isChain_iff_getElem- A list forms a chain under relation $R$ if and only if every element is related to its immediate successor.
List.head?_map- The head of a mapped list is the image under the map of the head of the original list.
List.head?_range- The head of the range list $[0, \dots, n-1]$ is `none` if $n = 0$, and `some 0` otherwise.
List.getLast?_map- The last element of a mapped list is the image under the map of the last element of the original list.
List.getLast?_range- The last element of the range list $[0, \dots, n-1]$ is `none` if $n = 0$, and `some (n - 1)` otherwise.
List.mem_toFinset- An element belongs to the Finset of a list if and only if it belongs to the list.
List.mem_map- An element belongs to a mapped list if and only if it is the image of some element in the original list.
digraph_low_cut_contains_cycle_outdeg_cycle- In a finite loopless digraph, any nonempty vertex set where every vertex has an out-neighbour in the set contains a directed cycle.
Fin.elim0- From an element of the empty type $\mathrm{Fin}(0)$, any proposition follows vacuously.
Finset.card_pos- A finite set is nonempty if and only if its cardinality is strictly positive.
digraph_low_cut_contains_cycle_sink- A finite nonempty vertex set containing no directed cycle in a loopless digraph contains a sink vertex with no out-neighbours in the set.
Finset.erase_subset- Erasing an element from a finite set produces a subset of the original set.
Finset.card_erase_of_mem- Erasing a member of a finite set decreases its cardinality by 1.
Fin.cons_injective_of_injective- Prepending an element not in the range of an injective map yields an injective map on the extended domain.
Finset.mem_erase- An element belongs to $s \setminus \{b\}$ if and only if it is not equal to $b$ and belongs to $s$.
Fin.cases- Proof by cases for $\mathrm{Fin}(n+1)$, distinguishing index 0 from successor indices.
Fin.cons_zero- Evaluating a prepended sequence $\mathrm{Fin.cons}(x_0, x)$ at 0 yields $x_0$.
Fin.cons_succ- Evaluating a prepended sequence $\mathrm{Fin.cons}(x_0, x)$ at successor index $i+1$ yields $x(i)$.
Finset.filter_eq_empty_iff- The filter of a set by a predicate is empty if and only if no element of the set satisfies the predicate.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the set and satisfies the filter condition.
Finset.mem_union- An element belongs to a union of sets if and only if it belongs to at least one of the sets.
Finset.card_le_card- If $s \subseteq t$, then $|s| \le |t|$ for finite sets.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.card_singleton- A singleton set has cardinality 1.
Fin.val_succ- The numerical value of the successor index $(j : \mathrm{Fin}\, n).\mathrm{succ}$ equals $j + 1$.
digraph_low_cut_contains_cycle_peel- From a cycle-free vertex set of size at least $r$ in a loopless digraph, one can select $r$ distinct vertices such that the $j$-th vertex has at most $j$ out-neighbours in the set.
Finset.disjoint_left- Two sets are disjoint if and only if every element of the first set is not in the second.
Finset.mem_compl- An element belongs to the complement $s^c$ if and only if it does not belong to $s$.
Finset.filter_union- Filtering a union of sets distributes over the union.
Finset.union_compl- The union of a set and its complement is the universe: $s \cup s^c = \mathrm{univ}$.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.sum_le_sum- If $f(i) \le g(i)$ for all elements $i$ in a finite set, then $\sum f(i) \le \sum g(i)$.
digraph_low_cut_contains_cycle_sum_fin- The sum $\sum_{j=0}^{r-1} (r - j)$ equals $r(r+1)/2$.
Finset.sum_image- Summing a function over the image of an injective map equals summing the composed function over the domain.
Finset.sum_le_sum_of_subset_of_nonneg- If $s \subseteq t$ and terms outside $s$ are non-negative, then the sum over $s$ is at most the sum over $t$.
Finset.image_subset_iff- The image $f(s)$ is a subset of $t$ if and only if $f(x) \in t$ for every $x \in s$.
Nat.zero_le- Every natural number is greater than or equal to 0.
le_trans- Inequality on ordered types is transitive: if $a \le b$ and $b \le c$, then $a \le c$.
absurd- From a proposition and its negation, any conclusion follows.
not_lt- For natural numbers, not strictly less than means greater than or equal to: $\neg (a < b) \leftrightarrow b \le a$.
- Several arithmetic identities and inequalities are discharged by `omega` (Presburger linear arithmetic) and `ring` (polynomial ring identity).
- The formal proof establishes four modular lemmas prior to the main theorem: the sum identity `digraph_low_cut_contains_cycle_sum_fin`, cycle existence in sets with positive internal out-degrees `digraph_low_cut_contains_cycle_outdeg_cycle`, sink existence in acyclic sets `digraph_low_cut_contains_cycle_sink`, and vertex peeling `digraph_low_cut_contains_cycle_peel`.
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.
/-- The sum of `r - j` over `j : Fin r` is `r * (r + 1) / 2`. -/theorem digraph_low_cut_contains_cycle_sum_fin (r : ℕ) : (∑ j : Fin r, (r - (j:ℕ))) = r * (r + 1) / 2 := by have h1 : (∑ j : Fin r, (r - (j:ℕ))) = ∑ k ∈ Finset.range r, (r - k) := by rw [Finset.sum_fin_eq_sum_range] refine Finset.sum_congr rfl ?_ intro k hk simp only [Finset.mem_range] at hk simp [hk] rw [h1] have h2 : ∑ k ∈ Finset.range r, (r - k) = ∑ k ∈ Finset.range r, (k + 1) := by have := Finset.sum_range_reflect (fun k => k + 1) r rw [← this] refine Finset.sum_congr rfl ?_ intro k hk simp only [Finset.mem_range] at hk omega rw [h2] rw [Finset.sum_add_distrib] simp only [Finset.sum_const_nat (m := 1) (fun x _ => rfl), Finset.card_range, mul_one] rw [Finset.sum_range_id] apply Nat.eq_div_of_mul_eq_right (c := 2) (by norm_num) have h2even : r * (r - 1) = 2 * (r * (r - 1) / 2) := by rw [Nat.mul_comm 2, Nat.div_two_mul_two_of_even (Nat.even_mul_pred_self r)] have key : r * (r - 1) + 2 * r = r * (r + 1) := by cases r with | zero => simp | succ n => have hsub : n + 1 - 1 = n := by omega rw [hsub] ring rw [Nat.mul_add, ← h2even] exact key/-- A finite nonempty vertex set in which every vertex has an out-neighbour inside itcontains a directed cycle. -/theorem digraph_low_cut_contains_cycle_outdeg_cycle (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (X : Finset α) (hne : X.Nonempty) (hout : ∀ v ∈ X, ∃ w ∈ X, D.Adj v w) : ∃ C : Finset α, C ⊆ X ∧ digraph_directed_cycle_on D C := by let S := {x : α // x ∈ X} have hS : ∀ s : S, ∃ t : S, D.Adj s.1 t.1 := by intro s; obtain ⟨w, hw, hadj⟩ := hout s.1 s.2; exact ⟨⟨w, hw⟩, hadj⟩ let step : S → S := fun s => (hS s).choose have hstep : ∀ s : S, D.Adj s.1 (step s).1 := fun s => (hS s).choose_spec obtain ⟨v0, hv0⟩ := hne let s0 : S := ⟨v0, hv0⟩ 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 (x (t + 1)).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 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 (m + 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 (m + i) = x (m + j) := Subtype.ext hij have hi' : m + i < n := by omega have hj' : m + j < n := by omega have : m + i = m + j := hinj (m + i) hi' (m + 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 : m + (i + 1) = (m + i) + 1 := by omega rw [hrel]; exact hxadj (m + i) have hhead : l.head? = some (c 0) := by rw [List.head?_map, List.head?_range] have hk0 : k ≠ 0 := by omega simp [hk0] have hlast : l.getLast? = some (c (k - 1)) := by rw [List.getLast?_map, List.getLast?_range] have hk0 : k ≠ 0 := by omega simp [hk0] have hadj_last_head : D.Adj (c (k - 1)) (c 0) := by have h1 : m + (k - 1) = n - 1 := by omega have h2 : m + 0 = m := by omega show D.Adj (x (m + (k - 1))).1 (x (m + 0)).1 rw [h1, h2, hxmn] have hn : (n - 1) + 1 = n := by omega show D.Adj (x (n - 1)).1 (x n).1 rw [← hn]; 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 (m + i)).2/-- A finite nonempty vertex set containing no directed cycle has a vertex with noout-neighbour inside it. -/theorem digraph_low_cut_contains_cycle_sink (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (X : Finset α) (hne : X.Nonempty) (hac : ∀ C, C ⊆ X → ¬ digraph_directed_cycle_on D C) : ∃ s ∈ X, ∀ w ∈ X, ¬ D.Adj s w := by by_contra h push Not at h obtain ⟨C, hCX, hcyc⟩ := digraph_low_cut_contains_cycle_outdeg_cycle α D hloop X hne h exact hac C hCX hcyc/-- From a cycle-free vertex set of size at least `r` one can peel `r` vertices so that the`j`-th peeled vertex has at most `j` out-neighbours inside the set. -/theorem digraph_low_cut_contains_cycle_peel (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) : ∀ (r : ℕ) (X : Finset α), (∀ C, C ⊆ X → ¬ digraph_directed_cycle_on D C) → r ≤ X.card → ∃ s : Fin r → α, Function.Injective s ∧ (∀ j, s j ∈ X) ∧ ∀ j, (X.filter (fun w => D.Adj (s j) w)).card ≤ (j : ℕ) := by intro r induction r with | zero => intro X hac hr exact ⟨Fin.elim0, fun i => i.elim0, fun i => i.elim0, fun i => i.elim0⟩ | succ r ih => intro X hac hr have hne : X.Nonempty := Finset.card_pos.mp (by omega) obtain ⟨s0, hs0X, hsink⟩ := digraph_low_cut_contains_cycle_sink α D hloop X hne hac have hac' : ∀ C, C ⊆ X.erase s0 → ¬ digraph_directed_cycle_on D C := fun C hC => hac C (hC.trans (Finset.erase_subset s0 X)) have hr' : r ≤ (X.erase s0).card := by rw [Finset.card_erase_of_mem hs0X]; omega obtain ⟨s', hinj', hmem', hbound'⟩ := ih (X.erase s0) hac' hr' let s : Fin (r+1) → α := Fin.cons s0 s' refine ⟨s, ?_, ?_, ?_⟩ · show Function.Injective (Fin.cons s0 s') apply Fin.cons_injective_of_injective · rintro ⟨i, hi⟩ exact (Finset.mem_erase.mp (hmem' i)).1 hi · exact hinj' · intro j induction j using Fin.cases with | zero => simpa only [s, Fin.cons_zero] using hs0X | succ i => simpa only [s, Fin.cons_succ] using (Finset.mem_erase.mp (hmem' i)).2 · intro j induction j using Fin.cases with | zero => have hempty : X.filter (fun w => D.Adj (s 0) w) = ∅ := by simp only [s, Fin.cons_zero] rw [Finset.filter_eq_empty_iff] intro w hw exact hsink w hw rw [hempty] simp | succ i => simp only [s, Fin.cons_succ] have hsub : X.filter (fun w => D.Adj (s' i) w) ⊆ (X.erase s0).filter (fun w => D.Adj (s' i) w) ∪ ({s0} : Finset α) := by intro w hw simp only [Finset.mem_filter] at hw rw [Finset.mem_union] by_cases hw0 : w = s0 · right; simp [hw0] · left simp only [Finset.mem_filter, Finset.mem_erase] exact ⟨⟨hw0, hw.1⟩, hw.2⟩ have h1 := Finset.card_le_card hsub have h2 := Finset.card_union_le ((X.erase s0).filter (fun w => D.Adj (s' i) w)) ({s0} : Finset α) have h3 := hbound' i rw [Finset.card_singleton] at h2 simp only [Fin.val_succ] omegatheorem digraph_low_cut_contains_cycle (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (r : ℕ) (hloop : ∀ v, ¬ D.Adj v v) (hdeg : ∀ v, r ≤ (Finset.univ.filter fun w => D.Adj v w).card) (B : Finset α) (hB : r ≤ B.card) (hcut : (∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card) < r * (r + 1) / 2) : ∃ C : Finset α, C ⊆ B ∧ digraph_directed_cycle_on D C := by by_contra hno push Not at hno obtain ⟨s, hinj, hmem, hbound⟩ := digraph_low_cut_contains_cycle_peel α D hloop r B hno hB have hterm : ∀ j : Fin r, r - (j:ℕ) ≤ (Bᶜ.filter fun w => D.Adj (s j) w).card := by intro j have hout : r ≤ (Finset.univ.filter (fun w => D.Adj (s j) w)).card := hdeg (s j) have hint : (B.filter (fun w => D.Adj (s j) w)).card ≤ (j:ℕ) := hbound j have hdisj : Disjoint (B.filter (fun w => D.Adj (s j) w)) (Bᶜ.filter (fun w => D.Adj (s j) w)) := by rw [Finset.disjoint_left] intro x hx hx' simp only [Finset.mem_filter] at hx hx' exact (Finset.mem_compl.mp hx'.1) hx.1 have hunion : B.filter (fun w => D.Adj (s j) w) ∪ Bᶜ.filter (fun w => D.Adj (s j) w) = Finset.univ.filter (fun w => D.Adj (s j) w) := by rw [← Finset.filter_union, Finset.union_compl] have hpart : (Finset.univ.filter (fun w => D.Adj (s j) w)).card = (B.filter (fun w => D.Adj (s j) w)).card + (Bᶜ.filter (fun w => D.Adj (s j) w)).card := by rw [← hunion, Finset.card_union_of_disjoint hdisj] omega have hsum_ge : r * (r + 1) / 2 ≤ ∑ j : Fin r, (Bᶜ.filter fun w => D.Adj (s j) w).card := by have h1 : ∑ j : Fin r, (r - (j:ℕ)) ≤ ∑ j : Fin r, (Bᶜ.filter fun w => D.Adj (s j) w).card := Finset.sum_le_sum (fun j _ => hterm j) rwa [digraph_low_cut_contains_cycle_sum_fin r] at h1 have hsum_le : ∑ j : Fin r, (Bᶜ.filter fun w => D.Adj (s j) w).card ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card := by have himg : ∑ j : Fin r, (Bᶜ.filter fun w => D.Adj (s j) w).card = ∑ v ∈ (Finset.univ.image s), (Bᶜ.filter fun w => D.Adj v w).card := by rw [Finset.sum_image (f := fun v => (Bᶜ.filter fun w => D.Adj v w).card) (g := s) (s := Finset.univ) (fun i _ j _ h => hinj h)] rw [himg] exact Finset.sum_le_sum_of_subset_of_nonneg (Finset.image_subset_iff.mpr (fun j _ => hmem j)) (fun v _ _ => Nat.zero_le _) have hfinal : r * (r + 1) / 2 ≤ ∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card := le_trans hsum_ge hsum_le exact absurd hcut (not_lt.mpr hfinal)