AFTD Auto-Formalizing Theoretical Domains

digraph_low_cut_contains_cycle

theoremverified

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

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$.

  1. 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`).

    lines 4–18

    uses Finset.sum_fin_eq_sum_range, Finset.sum_congr, Finset.mem_range, Finset.sum_range_reflect

      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]
  2. 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`.

    lines 19–33

    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_add

      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
  3. 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'`.

    lines 43–53

    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)
  4. 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)$.

    lines 54–64

    uses not_injective_infinite_finite, lt_trichotomy

      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
  5. 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$.

    lines 65–80

    uses Nat.find_spec, Nat.find_min, lt_trichotomy

      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
  6. 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`.

    lines 81–93

    uses List.nodup_map_iff_inj_on, List.nodup_range, List.mem_range, Subtype.ext

      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
  7. 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.

    lines 94–118

    uses List.isChain_iff_getElem, List.head?_map, List.head?_range, List.getLast?_map, List.getLast?_range

      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)
  8. 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$.

    lines 119–123

    uses List.mem_toFinset, List.mem_map

      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
  9. 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.

    lines 133–136

    uses digraph_low_cut_contains_cycle_outdeg_cycle

      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
  10. 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.

    lines 148–152

    uses Fin.elim0

      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⟩
  11. 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`.

    lines 153–168

    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'
  12. 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$.

    lines 169–173

    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
  13. 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`.

    lines 174–201

    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
  14. 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$.

    lines 204–207

    uses digraph_low_cut_contains_cycle_peel

      by_contra hno
      push Not at hno
      obtain ⟨s, hinj, hmem, hbound⟩ :=
        digraph_low_cut_contains_cycle_peel α D hloop r B hno hB
  15. 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$.

    lines 208–223

    uses Finset.disjoint_left, Finset.mem_filter, Finset.mem_compl, Finset.filter_union, Finset.union_compl, Finset.card_union_of_disjoint

      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
  16. 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$.

    lines 224–227

    uses Finset.sum_le_sum, digraph_low_cut_contains_cycle_sum_fin

      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
  17. 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$.

    lines 228–237

    uses Finset.sum_image, Finset.sum_le_sum_of_subset_of_nonneg, Finset.image_subset_iff, Nat.zero_le

      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 _)
  18. 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`.

    lines 238–240

    uses le_trans, absurd, not_lt

      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)
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$.

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

/-- 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)
See it in the graphDiscuss this resultChallenge it