AFTD Auto-Formalizing Theoretical Domains

digraph_cut20_sharp_example_certificate

theoremverified

In the displayed 20-vertex graph, the first 13 vertices all have outdegree seven, exactly 20 arcs leave that set, and it contains no two disjoint directed cycles. Moreover, every nonempty induced subset of minimum outdegree at least two has at least three vertices of internal outdegree below three.

Statement

theorem digraph_cut20_sharp_example_certificate :
    let D := digraph_cut20_sharp_example
    let B : Finset (Fin 20) := Finset.univ.filter fun v => v.val < 13
    (∀ v ∈ B, (Finset.univ.filter fun w => D.Adj v w).card = 7) ∧
    (∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card) = 20 ∧
    (¬ ∃ c : Fin 2 → Finset (Fin 20),
      (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j))) ∧
    (∀ T : Finset (Fin 20), T.Nonempty →
      (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) →
      3 ≤ (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card)
Source
Extension of https://arxiv.org/abs/2205.10826, Figure 3.2; experiments 26197 and 26198.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • digraph_cut20_sharp_exampleAn explicit 20-vertex digraph obtained by adjoining seven sink vertices to the displayed 13-vertex two-cycle obstruction.
  • 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 1

The proof, explained

The 20-vertex digraph is constructed around a 7-cycle core {0, ..., 6}, an apex vertex 7 pointing to all core vertices, five transition vertices {8, ..., 12}, and seven sinks {13, ..., 19}. The outdegree-7 regularity of B = {0, ..., 12} and the cut size of 20 are verified by finite computation (`decide`). To show that B contains no two disjoint directed cycles, any cycle avoiding the apex 7 triggers an elimination of vertices 8 through 12, forcing it to contain the entire core {0, ..., 6}; since every cycle in B must intersect this core, two disjoint cycles cannot exist. Finally, any nonempty induced subgraph with minimum outdegree at least 2 cannot contain sinks or vertices in {8, ..., 12} (by considering a minimal element), forcing it to be exactly {0, ..., 7}, where all seven core vertices have internal outdegree 2.

  1. Adjacency in digraph_cut20_sharp_example is decidable.

    By unfolding the definition of the adjacency relation—which consists of boolean combinations of inequalities and modular arithmetic on finite indices in Fin 20—Lean synthesizes a DecidableRel instance.

    lines 5–6

      unfold digraph_cut20_sharp_example
      infer_instance
  2. The vertex set C of any directed cycle is nonempty, containing the head vertex a of its defining path.

    Unpacking the definition of a directed cycle gives a chain l whose elements form C. Case analysis on l shows that its head vertex a belongs to l, and therefore a ∈ C, proving that C is nonempty.

    lines 11–20

    uses List.head?_cons, Option.some.injEq, List.mem_toFinset

      obtain ⟨l, hnodup, hlen, hset, hchain, a, b, hhead, hlast, hclose⟩ := hC
      have ha : a ∈ l := by
        cases l with
        | nil => simp at hhead
        | cons x xs =>
          simp only [List.head?_cons, Option.some.injEq] at hhead
          subst a
          simp
      have haC : a ∈ C := by rw [← hset, List.mem_toFinset]; exact ha
      refine ⟨⟨a, haC⟩, ?_⟩
  3. Every vertex v in a directed cycle has an in-cycle successor w such that (v, w) is a directed edge.

    Representing v as the element at index i in the cycle path l, if i + 1 < length(l), the next element l[i+1] belongs to C and the chain condition gives an edge from v to l[i+1]. If v is the last element (i = length(l) - 1), the closing edge connects it to the head vertex a ∈ C.

    lines 21–36

    uses List.mem_toFinset, List.getElem_of_mem, List.getElem_mem, List.getLast?_eq_getElem?, List.getElem?_eq_getElem

      intro v hv
      have hvL : v ∈ l := by rw [← hset, List.mem_toFinset] at hv; exact hv
      obtain ⟨i, hi, heq⟩ := List.getElem_of_mem hvL
      by_cases his : i + 1 < l.length
      · refine ⟨l[i+1], ?_, ?_⟩
        · rw [← hset, List.mem_toFinset]
          exact List.getElem_mem _
        · rw [← heq]
          exact hchain.getElem i his
      · have hilast : i = l.length - 1 := by omega
        have hidx : l[i]? = some b := by
          simpa [List.getLast?_eq_getElem?, ← hilast] using hlast
        have heqB : l[i] = b := by simpa [List.getElem?_eq_getElem hi] using hidx
        refine ⟨a, haC, ?_⟩
        rw [← heq, heqB]
        exact hclose
  4. Any directed cycle C ⊆ {0, ..., 12} that avoids vertex 7 is entirely contained in the core {0, ..., 6}.

    Every vertex in C has an in-cycle successor. The only outgoing edge from vertex 8 into {0, ..., 12} leads to 7, which is not in C, so 8 ∉ C. Outgoing edges from 9 lead only to 7 and 8, neither of which is in C, so 9 ∉ C. Continuing sequentially for vertices 10, 11, and 12 eliminates each from C. Hence all vertices of C must have index strictly less than 7.

    lines 42–162

    uses in833_cycle_successor, Fin.ext, False.elim

      obtain ⟨hne, hs⟩ := in833_cycle_successor digraph_cut20_sharp_example C hC
      have h8 : (8 : Fin 20) ∉ C := by
        intro hv
        obtain ⟨w, hw, hadj⟩ := hs 8 hv
        have hwB := hB w hw
        have heq : w.val = 7 := by
          change ((8 : Fin 20).val < 7 ∧ (w.val = ((8 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨
            ((8 : Fin 20).val = 7 ∧ w.val < 7) ∨
            (8 ≤ (8 : Fin 20).val ∧ (8 : Fin 20).val < 13 ∧
              (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (8 : Fin 20).val) ∨ (13 ≤ w.val ∧ (8 : Fin 20).val + w.val < 27))) at hadj
          omega
        apply h7
        have h : w = (7 : Fin 20) := Fin.ext heq
        simpa [h] using hw
      have h9 : (9 : Fin 20) ∉ C := by
        intro hv
        obtain ⟨w, hw, hadj⟩ := hs 9 hv
        have hwB := hB w hw
        have hw8 : w.val ≠ 8 := by
          intro heq
          apply h8
          have h : w = (8 : Fin 20) := Fin.ext heq
          simpa [h] using hw
        have heq : w.val = 7 := by
          change ((9 : Fin 20).val < 7 ∧ (w.val = ((9 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨
            ((9 : Fin 20).val = 7 ∧ w.val < 7) ∨
            (8 ≤ (9 : Fin 20).val ∧ (9 : Fin 20).val < 13 ∧
              (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (9 : Fin 20).val) ∨ (13 ≤ w.val ∧ (9 : Fin 20).val + w.val < 27))) at hadj
          omega
        apply h7
        have h : w = (7 : Fin 20) := Fin.ext heq
        simpa [h] using hw
      have h10 : (10 : Fin 20) ∉ C := by
        intro hv
        obtain ⟨w, hw, hadj⟩ := hs 10 hv
        have hwB := hB w hw
        have hw8 : w.val ≠ 8 := by
          intro heq
          apply h8
          have h : w = (8 : Fin 20) := Fin.ext heq
          simpa [h] using hw
        have hw9 : w.val ≠ 9 := by
          intro heq
          apply h9
          have h : w = (9 : Fin 20) := Fin.ext heq
          simpa [h] using hw
        have heq : w.val = 7 := by
          change ((10 : Fin 20).val < 7 ∧ (w.val = ((10 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨
            ((10 : Fin 20).val = 7 ∧ w.val < 7) ∨
            (8 ≤ (10 : Fin 20).val ∧ (10 : Fin 20).val < 13 ∧
              (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (10 : Fin 20).val) ∨ (13 ≤ w.val ∧ (10 : Fin 20).val + w.val < 27))) at hadj
          omega
        apply h7
        have h : w = (7 : Fin 20) := Fin.ext heq
        simpa [h] using hw
      have h11 : (11 : Fin 20) ∉ C := by
        intro hv
        obtain ⟨w, hw, hadj⟩ := hs 11 hv
        have hwB := hB w hw
        have hw8 : w.val ≠ 8 := by
          intro heq
          apply h8
          have h : w = (8 : Fin 20) := Fin.ext heq
          simpa [h] using hw
        have hw9 : w.val ≠ 9 := by
          intro heq
          apply h9
          have h : w = (9 : Fin 20) := Fin.ext heq
          simpa [h] using hw
        have hw10 : w.val ≠ 10 := by
          intro heq
          apply h10
          have h : w = (10 : Fin 20) := Fin.ext heq
          simpa [h] using hw
        have heq : w.val = 7 := by
          change ((11 : Fin 20).val < 7 ∧ (w.val = ((11 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨
            ((11 : Fin 20).val = 7 ∧ w.val < 7) ∨
            (8 ≤ (11 : Fin 20).val ∧ (11 : Fin 20).val < 13 ∧
              (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (11 : Fin 20).val) ∨ (13 ≤ w.val ∧ (11 : Fin 20).val + w.val < 27))) at hadj
          omega
        apply h7
        have h : w = (7 : Fin 20) := Fin.ext heq
        simpa [h] using hw
      have h12 : (12 : Fin 20) ∉ C := by
        intro hv
        obtain ⟨w, hw, hadj⟩ := hs 12 hv
        have hwB := hB w hw
        have hw8 : w.val ≠ 8 := by
          intro heq
          apply h8
          have h : w = (8 : Fin 20) := Fin.ext heq
          simpa [h] using hw
        have hw9 : w.val ≠ 9 := by
          intro heq
          apply h9
          have h : w = (9 : Fin 20) := Fin.ext heq
          simpa [h] using hw
        have hw10 : w.val ≠ 10 := by
          intro heq
          apply h10
          have h : w = (10 : Fin 20) := Fin.ext heq
          simpa [h] using hw
        have hw11 : w.val ≠ 11 := by
          intro heq
          apply h11
          have h : w = (11 : Fin 20) := Fin.ext heq
          simpa [h] using hw
        have heq : w.val = 7 := by
          change ((12 : Fin 20).val < 7 ∧ (w.val = ((12 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨
            ((12 : Fin 20).val = 7 ∧ w.val < 7) ∨
            (8 ≤ (12 : Fin 20).val ∧ (12 : Fin 20).val < 13 ∧
              (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (12 : Fin 20).val) ∨ (13 ≤ w.val ∧ (12 : Fin 20).val + w.val < 27))) at hadj
          omega
        apply h7
        have h : w = (7 : Fin 20) := Fin.ext heq
        simpa [h] using hw
      have hcore : ∀ v ∈ C, v.val < 7 := by
        intro v hv
        have hvB := hB v hv
        fin_cases v <;> norm_num at hvB <;> norm_num <;>
          first | exact False.elim (h7 (by simpa using hv)) | exact False.elim (h8 (by simpa using hv)) | exact False.elim (h9 (by simpa using hv)) | exact False.elim (h10 (by simpa using hv)) | exact False.elim (h11 (by simpa using hv)) | exact False.elim (h12 (by simpa using hv))
  5. For every vertex v in C, the directed successor (v + 1) mod 7 along the core cycle belongs to C.

    The outgoing edges from any core vertex v < 7 go only to (v + 1) mod 7, to apex vertex 7, or to vertices in {8, ..., 12}. Since C contains neither 7 nor any vertex ≥ 8, the in-cycle successor of v must be (v + 1) mod 7.

    lines 163–175

    uses Nat.mod_lt, Fin.ext

      have hstep (v : Fin 20) (hv : v ∈ C) :
          (⟨(v.val + 1) % 7, by have := Nat.mod_lt (v.val+1) (by norm_num : 0 < 7); omega⟩ : Fin 20) ∈ C := by
        obtain ⟨w, hw, hadj⟩ := hs v hv
        have hvcore := hcore v hv
        have hwcore := hcore w hw
        have heq : w.val = (v.val + 1) % 7 := by
          change (v.val < 7 ∧ (w.val = (v.val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨
            (v.val = 7 ∧ w.val < 7) ∨
            (8 ≤ v.val ∧ v.val < 13 ∧
              (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < v.val) ∨ (13 ≤ w.val ∧ v.val + w.val < 27))) at hadj
          omega
        have hw' : w = (⟨(v.val + 1) % 7, by have := Nat.mod_lt (v.val+1) (by norm_num : 0 < 7); omega⟩ : Fin 20) := Fin.ext heq
        simpa [← hw'] using hw
  6. The cycle C contains every core vertex {0, ..., 6}.

    If 0 were not in C, then since the successor of 6 is 0, vertex 6 could not be in C; by backwards induction along the 7-cycle, vertices 5, 4, 3, 2, and 1 would also be excluded, leaving C empty and contradicting nonemptiness. Thus 0 ∈ C. Propagating forward via the successor step then shows that 1, 2, 3, 4, 5, and 6 all belong to C.

    lines 176–214

      have h0 : (0 : Fin 20) ∈ C := by
        by_contra h0
        have h6 : (6 : Fin 20) ∉ C := by
          intro h
          apply h0
          simpa using hstep 6 h
        have h5 : (5 : Fin 20) ∉ C := by
          intro h
          apply h6
          simpa using hstep 5 h
        have h4 : (4 : Fin 20) ∉ C := by
          intro h
          apply h5
          simpa using hstep 4 h
        have h3 : (3 : Fin 20) ∉ C := by
          intro h
          apply h4
          simpa using hstep 3 h
        have h2 : (2 : Fin 20) ∉ C := by
          intro h
          apply h3
          simpa using hstep 2 h
        have h1 : (1 : Fin 20) ∉ C := by
          intro h
          apply h2
          simpa using hstep 1 h
        obtain ⟨v,hv⟩ := hne
        have hvcore := hcore v hv
        fin_cases v <;> norm_num at hvcore <;>
          first | exact h0 (by simpa using hv) | exact h1 (by simpa using hv) | exact h2 (by simpa using hv) | exact h3 (by simpa using hv) | exact h4 (by simpa using hv) | exact h5 (by simpa using hv) | exact h6 (by simpa using hv)
      have h1 : (1 : Fin 20) ∈ C := by simpa using hstep 0 h0
      have h2 : (2 : Fin 20) ∈ C := by simpa using hstep 1 h1
      have h3 : (3 : Fin 20) ∈ C := by simpa using hstep 2 h2
      have h4 : (4 : Fin 20) ∈ C := by simpa using hstep 3 h3
      have h5 : (5 : Fin 20) ∈ C := by simpa using hstep 4 h4
      have h6 : (6 : Fin 20) ∈ C := by simpa using hstep 5 h5
      intro v hv
      fin_cases v <;> norm_num at hv <;>
        first | simpa using h0 | simpa using h1 | simpa using h2 | simpa using h3 | simpa using h4 | simpa using h5 | simpa using h6
  7. Every directed cycle C ⊆ {0, ..., 12} contains at least one vertex from the core {0, ..., 6}.

    If 7 ∈ C, its successor in C must belong to {0, ..., 6} because all edges leaving 7 lead to the core. If 7 ∉ C, the previous lemma shows that all of {0, ..., 6} belongs to C, so vertex 0 is in C.

    lines 220–229

    uses in833_cycle_successor, in833_cut20_cycle_no_apex_core

      by_cases h7 : (7 : Fin 20) ∈ C
      · obtain ⟨_, hs⟩ := in833_cycle_successor digraph_cut20_sharp_example C hC
        obtain ⟨w,hw,hadj⟩ := hs 7 h7
        refine ⟨w,hw,?_⟩
        change ((7 : Fin 20).val < 7 ∧ (w.val = ((7 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨
          ((7 : Fin 20).val = 7 ∧ w.val < 7) ∨
          (8 ≤ (7 : Fin 20).val ∧ (7 : Fin 20).val < 13 ∧
            (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (7 : Fin 20).val) ∨ (13 ≤ w.val ∧ (7 : Fin 20).val + w.val < 27))) at hadj
        omega
      · exact ⟨0, in833_cut20_cycle_no_apex_core C hC hB h7 0 (by norm_num), by norm_num⟩
  8. There do not exist two vertex-disjoint directed cycles c₀ and c₁ in B = {0, ..., 12}.

    Suppose two such disjoint cycles exist. Apex 7 cannot belong to both. Whichever cycle avoids 7 must contain all core vertices {0, ..., 6} by in833_cut20_cycle_no_apex_core. But the other cycle must also contain at least one core vertex by in833_cut20_cycle_has_core. Their intersection is therefore nonempty, contradicting disjointness.

    lines 237–252

    uses Finset.disjoint_left.mp, in833_cut20_cycle_has_core, in833_cut20_cycle_no_apex_core

      dsimp only
      intro ⟨c,hc,hdis⟩
      have hdis01 : Disjoint (c 0) (c 1) := hdis (by decide)
      have hB (i : Fin 2) : ∀ v ∈ c i, v.val < 13 := by
        intro v hv
        have h := (hc i).1 hv
        simpa using h
      by_cases h70 : (7 : Fin 20) ∈ c 0
      · by_cases h71 : (7 : Fin 20) ∈ c 1
        · exact (Finset.disjoint_left.mp hdis01) h70 h71
        · obtain ⟨v,hv,hv7⟩ := in833_cut20_cycle_has_core (c 0) (hc 0).2 (hB 0)
          have hv' := in833_cut20_cycle_no_apex_core (c 1) (hc 1).2 (hB 1) h71 v hv7
          exact (Finset.disjoint_left.mp hdis01) hv hv'
      · obtain ⟨v,hv,hv7⟩ := in833_cut20_cycle_has_core (c 1) (hc 1).2 (hB 1)
        have hv' := in833_cut20_cycle_no_apex_core (c 0) (hc 0).2 (hB 0) h70 v hv7
        exact (Finset.disjoint_left.mp hdis01) hv' hv
  9. Every vertex in any nonempty induced subgraph T with minimum internal outdegree at least 2 belongs to B = {0, ..., 12}.

    Vertices v ≥ 13 are sinks with outdegree 0 in the entire graph, so their outdegree in T is 0, which contradicts the hypothesis that every vertex in T has internal outdegree at least 2.

    lines 259–276

      dsimp only
      intro T hne hdeg
      have hsink (v : Fin 20) (hv : v ∈ T) : v.val < 13 := by
        by_contra h
        have hfalse : ∀ w : Fin 20, ¬ digraph_cut20_sharp_example.Adj v w := by
          intro w
          change ¬ ((v.val < 7 ∧ (w.val = (v.val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨
            (v.val = 7 ∧ w.val < 7) ∨
            (8 ≤ v.val ∧ v.val < 13 ∧
              (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < v.val) ∨ (13 ≤ w.val ∧ v.val + w.val < 27))))
          omega
        have he : T.filter (fun w => digraph_cut20_sharp_example.Adj v w) = ∅ := by
          ext w
          simp [hfalse w]
        have hh := hdeg v hv
        rw [he] at hh
        simp at hh
      have hbound (v : Fin 20) (hv : v ∈ T) : v.val < 8 := by
  10. Every vertex in T satisfies v < 8, so T ⊆ {0, ..., 7}.

    Suppose for contradiction that T contains vertices ≥ 8, and let u be the minimum such vertex. Out-neighbors of u in T cannot be sinks (≥ 13) and cannot lie in {8, ..., u - 1} by minimality of u. Thus the only possible out-neighbor of u in T is vertex 7, which gives u internal outdegree at most 1, contradicting the degree assumption.

    lines 277–308

    uses Finset.mem_filter.mpr, Finset.min'_mem, Finset.mem_filter.mp, Finset.min'_le, Fin.ext, Finset.card_le_card, Finset.card_singleton

        by_contra hh
        let U := T.filter fun w => 8 ≤ w.val
        have hU : U.Nonempty := ⟨v, Finset.mem_filter.mpr ⟨hv, by omega⟩⟩
        let u := U.min' hU
        have hu : u ∈ U := Finset.min'_mem U hU
        have huT : u ∈ T := (Finset.mem_filter.mp hu).1
        have hu8 : 8 ≤ u.val := (Finset.mem_filter.mp hu).2
        have hu13 := hsink u huT
        have hsub : T.filter (fun w => digraph_cut20_sharp_example.Adj u w) ⊆ {7} := by
          intro w hw
          have hwT : w ∈ T := (Finset.mem_filter.mp hw).1
          have hadj := (Finset.mem_filter.mp hw).2
          have hw13 := hsink w hwT
          have hnot : ¬ (8 ≤ w.val ∧ w.val < u.val) := by
            intro h
            have hwU : w ∈ U := Finset.mem_filter.mpr ⟨hwT,h.1⟩
            have hmin := Finset.min'_le U w hwU
            have : u.val ≤ w.val := hmin
            omega
          have heq : w.val = 7 := by
            change (u.val < 7 ∧ (w.val = (u.val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨
              (u.val = 7 ∧ w.val < 7) ∨
              (8 ≤ u.val ∧ u.val < 13 ∧
                (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < u.val) ∨ (13 ≤ w.val ∧ u.val + w.val < 27))) at hadj
            omega
          have : w = (7 : Fin 20) := Fin.ext heq
          simpa [this]
        have hle := Finset.card_le_card hsub
        simp only [Finset.card_singleton] at hle
        have hge := hdeg u huT
        omega
      have hcard : 2 ≤ T.card := by
  11. The set T has cardinality at least 2 and contains at least one core vertex from {0, ..., 6}.

    Since each vertex in T has at least 2 out-neighbors in T, |T| ≥ 2. If no vertex in T were in {0, ..., 6}, then together with T ⊆ {0, ..., 7} we would have T ⊆ {7}, meaning |T| ≤ 1, a contradiction.

    lines 309–324

    uses Finset.card_le_card, Finset.filter_subset, Fin.ext, Finset.card_singleton

        obtain ⟨v,hv⟩ := hne
        have hh := hdeg v hv
        have hsub := Finset.card_le_card (Finset.filter_subset (fun w => digraph_cut20_sharp_example.Adj v w) T)
        omega
      have hcore : ∃ v ∈ T, v.val < 7 := by
        by_contra hh
        push_neg at hh
        have hsub : T ⊆ {7} := by
          intro v hv
          have h1 := hbound v hv
          have h2 := hh v hv
          have : v = (7 : Fin 20) := Fin.ext (by omega)
          simpa [this]
        have hle := Finset.card_le_card hsub
        simp only [Finset.card_singleton] at hle
        omega
  12. For any core vertex v ∈ T, both the apex 7 and the successor (v + 1) mod 7 belong to T.

    For v < 7, all out-neighbors in the graph outside {7, (v + 1) mod 7} are in {8, ..., 12}, which do not intersect T. Since v has at least 2 out-neighbors in T, both 7 and (v + 1) mod 7 must be in T.

    lines 325–365

    uses Nat.mod_lt, Or.inl, Or.inr, Fin.ext, Finset.mem_filter.mp, Finset.card_le_card, Finset.card_singleton

      have hstep (v : Fin 20) (hv : v ∈ T) (hv7 : v.val < 7) :
          (7 : Fin 20) ∈ T ∧
          (⟨(v.val + 1) % 7, by have := Nat.mod_lt (v.val+1) (by norm_num : 0 < 7); omega⟩ : Fin 20) ∈ T := by
        let next : Fin 20 := ⟨(v.val+1)%7, by have := Nat.mod_lt (v.val+1) (by norm_num : 0 < 7); omega⟩
        have hout : ∀ w ∈ T, digraph_cut20_sharp_example.Adj v w → w = 7 ∨ w = next := by
          intro w hw hadj
          have hw8 := hbound w hw
          have hval : w.val = 7 ∨ w.val = (v.val+1)%7 := by
            change (v.val < 7 ∧ (w.val = (v.val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨
              (v.val = 7 ∧ w.val < 7) ∨
              (8 ≤ v.val ∧ v.val < 13 ∧
                (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < v.val) ∨ (13 ≤ w.val ∧ v.val + w.val < 27))) at hadj
            omega
          rcases hval with h | h
          · exact Or.inl (Fin.ext h)
          · exact Or.inr (Fin.ext h)
        have hfilter := hdeg v hv
        constructor
        · by_contra h7
          have hsub : T.filter (fun w => digraph_cut20_sharp_example.Adj v w) ⊆ {next} := by
            intro w hw
            obtain ⟨hwT,hadj⟩ := Finset.mem_filter.mp hw
            rcases hout w hwT hadj with heq | heq
            · subst w; contradiction
            · simpa [heq]
          have hh := Finset.card_le_card hsub
          simp only [Finset.card_singleton] at hh
          omega
        · by_contra hn
          have hsub : T.filter (fun w => digraph_cut20_sharp_example.Adj v w) ⊆ {7} := by
            intro w hw
            obtain ⟨hwT,hadj⟩ := Finset.mem_filter.mp hw
            rcases hout w hwT hadj with heq | heq
            · simpa [heq]
            · subst w; contradiction
          have hh := Finset.card_le_card hsub
          simp only [Finset.card_singleton] at hh
          omega
      have h0 : (0 : Fin 20) ∈ T := by
        by_contra h0
        have h6 : (6 : Fin 20) ∉ T := by
  13. The set T must be exactly the 8-element set {0, 1, 2, 3, 4, 5, 6, 7}.

    Since T contains some core vertex, backwards induction along the 7-cycle forces 0 ∈ T (otherwise all core vertices would be absent, contradiction). Propagating forward via the successor property then shows 1, 2, 3, 4, 5, 6, and 7 all belong to T, so T = {0, ..., 7}.

    lines 366–407

    uses Finset.mem_filter.mpr, Finset.mem_univ, Finset.mem_filter.mp

          intro h
          apply h0
          simpa using (hstep 6 h (by norm_num)).2
        have h5 : (5 : Fin 20) ∉ T := by
          intro h
          apply h6
          simpa using (hstep 5 h (by norm_num)).2
        have h4 : (4 : Fin 20) ∉ T := by
          intro h
          apply h5
          simpa using (hstep 4 h (by norm_num)).2
        have h3 : (3 : Fin 20) ∉ T := by
          intro h
          apply h4
          simpa using (hstep 3 h (by norm_num)).2
        have h2 : (2 : Fin 20) ∉ T := by
          intro h
          apply h3
          simpa using (hstep 2 h (by norm_num)).2
        have h1 : (1 : Fin 20) ∉ T := by
          intro h
          apply h2
          simpa using (hstep 1 h (by norm_num)).2
        obtain ⟨v,hv,hv7⟩ := hcore
        fin_cases v <;> norm_num at hv7 <;>
          first | exact h0 (by simpa using hv) | exact h1 (by simpa using hv) | exact h2 (by simpa using hv) | exact h3 (by simpa using hv) | exact h4 (by simpa using hv) | exact h5 (by simpa using hv) | exact h6 (by simpa using hv)
      have h1 : (1 : Fin 20) ∈ T := by simpa using (hstep 0 h0 (by norm_num)).2
      have h2 : (2 : Fin 20) ∈ T := by simpa using (hstep 1 h1 (by norm_num)).2
      have h3 : (3 : Fin 20) ∈ T := by simpa using (hstep 2 h2 (by norm_num)).2
      have h4 : (4 : Fin 20) ∈ T := by simpa using (hstep 3 h3 (by norm_num)).2
      have h5 : (5 : Fin 20) ∈ T := by simpa using (hstep 4 h4 (by norm_num)).2
      have h6 : (6 : Fin 20) ∈ T := by simpa using (hstep 5 h5 (by norm_num)).2
      have h7 : (7 : Fin 20) ∈ T := (hstep 0 h0 (by norm_num)).1
      have hT : T = Finset.univ.filter (fun v : Fin 20 => v.val < 8) := by
        ext v
        constructor
        · intro hv
          exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hbound v hv⟩
        · intro hv
          have hv' := (Finset.mem_filter.mp hv).2
          fin_cases v <;> norm_num at hv' <;>
            first | simpa using h0 | simpa using h1 | simpa using h2 | simpa using h3 | simpa using h4 | simpa using h5 | simpa using h6 | simpa using h7
  14. The induced subgraph on T = {0, ..., 7} has at least 3 vertices of internal outdegree strictly less than 3. automation

    Rewriting T as {0, ..., 7}, Lean's decide tactic verifies by finite evaluation that all 7 core vertices have internal outdegree exactly 2 (pointing only to their cycle successor and the apex 7), so the number of vertices with outdegree below 3 is 7 ≥ 3.

    lines 408–409

      rw [hT]
      decide
  15. Every vertex in B = {0, ..., 12} has outdegree exactly 7. automation

    Verified directly by finite enumeration over all 13 vertices of B using decide.

    line 415

      decide
  16. Exactly 20 directed edges go from B to its complement. automation

    Verified directly by summing the outdegrees into Bᶜ across all vertices in B using decide.

    line 421

      decide
  17. The certificate theorem holds: B is 7-regular, the cut from B has size 20, B contains no two disjoint directed cycles, and any induced subgraph of minimum outdegree at least 2 has at least 3 vertices of internal outdegree under 3.

    Combines the four established lemmas into a conjunction.

    line 434

    uses in833_cut20_degree, in833_cut20_boundary, in833_cut20_no_two, in833_cut20_robust

      exact ⟨in833_cut20_degree, in833_cut20_boundary, in833_cut20_no_two, in833_cut20_robust⟩
Finset.disjoint_left.mp
If two sets are disjoint, an element belonging to the first cannot belong to the second.
Finset.filter_subset
Filtering a finite set by a predicate yields a subset of the original set.
Finset.card_le_card
A subset has cardinality at most that of the superset.
Finset.card_singleton
A singleton set has cardinality 1.
Finset.mem_filter.mp
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate (forward direction).
Finset.mem_filter.mpr
An element belongs to a filtered set if it belongs to the base set and satisfies the predicate (reverse direction).
Finset.mem_univ
Every element of a finite type belongs to the universal set.
Finset.min'_mem
The minimum element of a nonempty finite set belongs to the set.
Finset.min'_le
The minimum element of a finite set is less than or equal to every element in the set.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural values are equal.
False.elim
From a contradiction (False), any statement follows.
Nat.mod_lt
For any positive modulus y, the remainder x % y is strictly less than y.
Or.inl
Proves a disjunction A ∨ B from a proof of the left disjunct A.
Or.inr
Proves a disjunction A ∨ B from a proof of the right disjunct B.
List.head?_cons
The optional head of a cons list (a :: l) is some a.
List.getLast?_eq_getElem?
The optional last element of a list equals the element at index length - 1.
List.getElem?_eq_getElem
Looking up a valid index as an option returns some of the element at that index.
List.getElem_mem
Every element at a valid index of a list belongs to the list.
List.getElem_of_mem
An element belonging to a list occurs at some valid index in the list.
List.mem_toFinset
An element belongs to the Finset of a list if and only if it belongs to the list.
Option.some.injEq
some x = some y if and only if x = y.
in833_cycle_successor
Every vertex in a directed cycle has a successor in the cycle, and the cycle vertex set is nonempty.
in833_cut20_cycle_no_apex_core
Any directed cycle in B = {0, ..., 12} that avoids apex vertex 7 contains all core vertices {0, ..., 6}.
in833_cut20_cycle_has_core
Every directed cycle in B = {0, ..., 12} contains at least one core vertex from {0, ..., 6}.
in833_cut20_degree
Every vertex in B = {0, ..., 12} has outdegree 7 in the graph.
in833_cut20_boundary
The total number of directed arcs from B to its complement is 20.
in833_cut20_no_two
No two vertex-disjoint directed cycles exist in B = {0, ..., 12}.
in833_cut20_robust
Every nonempty induced subgraph of minimum outdegree at least 2 contains at least 3 vertices of internal outdegree under 3.

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

Lean’s trace was cut to the first 400 of 758 tactics.

set_option maxHeartbeats 3000000set_option maxRecDepth 4096private instance in833_cut20_scratch_decAdj : DecidableRel digraph_cut20_sharp_example.Adj := by  unfold digraph_cut20_sharp_example  infer_instanceprivate theorem in833_cycle_successor {α : Type} [DecidableEq α]    (D : Digraph α) (C : Finset α) (hC : digraph_directed_cycle_on D C) :    C.Nonempty ∧ ∀ v ∈ C, ∃ w ∈ C, D.Adj v w := by  obtain ⟨l, hnodup, hlen, hset, hchain, a, b, hhead, hlast, hclose⟩ := hC  have ha : a ∈ l := by    cases l with    | nil => simp at hhead    | cons x xs =>      simp only [List.head?_cons, Option.some.injEq] at hhead      subst a      simp  have haC : a ∈ C := by rw [← hset, List.mem_toFinset]; exact ha  refine ⟨⟨a, haC⟩, ?_⟩  intro v hv  have hvL : v ∈ l := by rw [← hset, List.mem_toFinset] at hv; exact hv  obtain ⟨i, hi, heq⟩ := List.getElem_of_mem hvL  by_cases his : i + 1 < l.length  · refine ⟨l[i+1], ?_, ?_⟩    · rw [← hset, List.mem_toFinset]      exact List.getElem_mem _    · rw [← heq]      exact hchain.getElem i his  · have hilast : i = l.length - 1 := by omega    have hidx : l[i]? = some b := by      simpa [List.getLast?_eq_getElem?, ← hilast] using hlast    have heqB : l[i] = b := by simpa [List.getElem?_eq_getElem hi] using hidx    refine ⟨a, haC, ?_⟩    rw [← heq, heqB]    exact hcloseprivate theorem in833_cut20_cycle_no_apex_core    (C : Finset (Fin 20)) (hC : digraph_directed_cycle_on digraph_cut20_sharp_example C)    (hB : ∀ v ∈ C, v.val < 13) (h7 : (7 : Fin 20) ∉ C) :    ∀ v : Fin 20, v.val < 7 → v ∈ C := by  obtain ⟨hne, hs⟩ := in833_cycle_successor digraph_cut20_sharp_example C hC  have h8 : (8 : Fin 20) ∉ C := by    intro hv    obtain ⟨w, hw, hadj⟩ := hs 8 hv    have hwB := hB w hw    have heq : w.val = 7 := by      change ((8 : Fin 20).val < 7 ∧ (w.val = ((8 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨        ((8 : Fin 20).val = 7 ∧ w.val < 7) ∨        (8 ≤ (8 : Fin 20).val ∧ (8 : Fin 20).val < 13 ∧          (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (8 : Fin 20).val) ∨ (13 ≤ w.val ∧ (8 : Fin 20).val + w.val < 27))) at hadj      omega    apply h7    have h : w = (7 : Fin 20) := Fin.ext heq    simpa [h] using hw  have h9 : (9 : Fin 20) ∉ C := by    intro hv    obtain ⟨w, hw, hadj⟩ := hs 9 hv    have hwB := hB w hw    have hw8 : w.val ≠ 8 := by      intro heq      apply h8      have h : w = (8 : Fin 20) := Fin.ext heq      simpa [h] using hw    have heq : w.val = 7 := by      change ((9 : Fin 20).val < 7 ∧ (w.val = ((9 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨        ((9 : Fin 20).val = 7 ∧ w.val < 7) ∨        (8 ≤ (9 : Fin 20).val ∧ (9 : Fin 20).val < 13 ∧          (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (9 : Fin 20).val) ∨ (13 ≤ w.val ∧ (9 : Fin 20).val + w.val < 27))) at hadj      omega    apply h7    have h : w = (7 : Fin 20) := Fin.ext heq    simpa [h] using hw  have h10 : (10 : Fin 20) ∉ C := by    intro hv    obtain ⟨w, hw, hadj⟩ := hs 10 hv    have hwB := hB w hw    have hw8 : w.val ≠ 8 := by      intro heq      apply h8      have h : w = (8 : Fin 20) := Fin.ext heq      simpa [h] using hw    have hw9 : w.val ≠ 9 := by      intro heq      apply h9      have h : w = (9 : Fin 20) := Fin.ext heq      simpa [h] using hw    have heq : w.val = 7 := by      change ((10 : Fin 20).val < 7 ∧ (w.val = ((10 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨        ((10 : Fin 20).val = 7 ∧ w.val < 7) ∨        (8 ≤ (10 : Fin 20).val ∧ (10 : Fin 20).val < 13 ∧          (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (10 : Fin 20).val) ∨ (13 ≤ w.val ∧ (10 : Fin 20).val + w.val < 27))) at hadj      omega    apply h7    have h : w = (7 : Fin 20) := Fin.ext heq    simpa [h] using hw  have h11 : (11 : Fin 20) ∉ C := by    intro hv    obtain ⟨w, hw, hadj⟩ := hs 11 hv    have hwB := hB w hw    have hw8 : w.val ≠ 8 := by      intro heq      apply h8      have h : w = (8 : Fin 20) := Fin.ext heq      simpa [h] using hw    have hw9 : w.val ≠ 9 := by      intro heq      apply h9      have h : w = (9 : Fin 20) := Fin.ext heq      simpa [h] using hw    have hw10 : w.val ≠ 10 := by      intro heq      apply h10      have h : w = (10 : Fin 20) := Fin.ext heq      simpa [h] using hw    have heq : w.val = 7 := by      change ((11 : Fin 20).val < 7 ∧ (w.val = ((11 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨        ((11 : Fin 20).val = 7 ∧ w.val < 7) ∨        (8 ≤ (11 : Fin 20).val ∧ (11 : Fin 20).val < 13 ∧          (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (11 : Fin 20).val) ∨ (13 ≤ w.val ∧ (11 : Fin 20).val + w.val < 27))) at hadj      omega    apply h7    have h : w = (7 : Fin 20) := Fin.ext heq    simpa [h] using hw  have h12 : (12 : Fin 20) ∉ C := by    intro hv    obtain ⟨w, hw, hadj⟩ := hs 12 hv    have hwB := hB w hw    have hw8 : w.val ≠ 8 := by      intro heq      apply h8      have h : w = (8 : Fin 20) := Fin.ext heq      simpa [h] using hw    have hw9 : w.val ≠ 9 := by      intro heq      apply h9      have h : w = (9 : Fin 20) := Fin.ext heq      simpa [h] using hw    have hw10 : w.val ≠ 10 := by      intro heq      apply h10      have h : w = (10 : Fin 20) := Fin.ext heq      simpa [h] using hw    have hw11 : w.val ≠ 11 := by      intro heq      apply h11      have h : w = (11 : Fin 20) := Fin.ext heq      simpa [h] using hw    have heq : w.val = 7 := by      change ((12 : Fin 20).val < 7 ∧ (w.val = ((12 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨        ((12 : Fin 20).val = 7 ∧ w.val < 7) ∨        (8 ≤ (12 : Fin 20).val ∧ (12 : Fin 20).val < 13 ∧          (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (12 : Fin 20).val) ∨ (13 ≤ w.val ∧ (12 : Fin 20).val + w.val < 27))) at hadj      omega    apply h7    have h : w = (7 : Fin 20) := Fin.ext heq    simpa [h] using hw  have hcore : ∀ v ∈ C, v.val < 7 := by    intro v hv    have hvB := hB v hv    fin_cases v <;> norm_num at hvB <;> norm_num <;>      first | exact False.elim (h7 (by simpa using hv)) | exact False.elim (h8 (by simpa using hv)) | exact False.elim (h9 (by simpa using hv)) | exact False.elim (h10 (by simpa using hv)) | exact False.elim (h11 (by simpa using hv)) | exact False.elim (h12 (by simpa using hv))  have hstep (v : Fin 20) (hv : v ∈ C) :      (⟨(v.val + 1) % 7, by have := Nat.mod_lt (v.val+1) (by norm_num : 0 < 7); omega⟩ : Fin 20) ∈ C := by    obtain ⟨w, hw, hadj⟩ := hs v hv    have hvcore := hcore v hv    have hwcore := hcore w hw    have heq : w.val = (v.val + 1) % 7 := by      change (v.val < 7 ∧ (w.val = (v.val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨        (v.val = 7 ∧ w.val < 7) ∨        (8 ≤ v.val ∧ v.val < 13 ∧          (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < v.val) ∨ (13 ≤ w.val ∧ v.val + w.val < 27))) at hadj      omega    have hw' : w = (⟨(v.val + 1) % 7, by have := Nat.mod_lt (v.val+1) (by norm_num : 0 < 7); omega⟩ : Fin 20) := Fin.ext heq    simpa [← hw'] using hw  have h0 : (0 : Fin 20) ∈ C := by    by_contra h0    have h6 : (6 : Fin 20) ∉ C := by      intro h      apply h0      simpa using hstep 6 h    have h5 : (5 : Fin 20) ∉ C := by      intro h      apply h6      simpa using hstep 5 h    have h4 : (4 : Fin 20) ∉ C := by      intro h      apply h5      simpa using hstep 4 h    have h3 : (3 : Fin 20) ∉ C := by      intro h      apply h4      simpa using hstep 3 h    have h2 : (2 : Fin 20) ∉ C := by      intro h      apply h3      simpa using hstep 2 h    have h1 : (1 : Fin 20) ∉ C := by      intro h      apply h2      simpa using hstep 1 h    obtain ⟨v,hv⟩ := hne    have hvcore := hcore v hv    fin_cases v <;> norm_num at hvcore <;>      first | exact h0 (by simpa using hv) | exact h1 (by simpa using hv) | exact h2 (by simpa using hv) | exact h3 (by simpa using hv) | exact h4 (by simpa using hv) | exact h5 (by simpa using hv) | exact h6 (by simpa using hv)  have h1 : (1 : Fin 20) ∈ C := by simpa using hstep 0 h0  have h2 : (2 : Fin 20) ∈ C := by simpa using hstep 1 h1  have h3 : (3 : Fin 20) ∈ C := by simpa using hstep 2 h2  have h4 : (4 : Fin 20) ∈ C := by simpa using hstep 3 h3  have h5 : (5 : Fin 20) ∈ C := by simpa using hstep 4 h4  have h6 : (6 : Fin 20) ∈ C := by simpa using hstep 5 h5  intro v hv  fin_cases v <;> norm_num at hv <;>    first | simpa using h0 | simpa using h1 | simpa using h2 | simpa using h3 | simpa using h4 | simpa using h5 | simpa using h6private theorem in833_cut20_cycle_has_core    (C : Finset (Fin 20)) (hC : digraph_directed_cycle_on digraph_cut20_sharp_example C)    (hB : ∀ v ∈ C, v.val < 13) :    ∃ v ∈ C, v.val < 7 := by  by_cases h7 : (7 : Fin 20) ∈ C  · obtain ⟨_, hs⟩ := in833_cycle_successor digraph_cut20_sharp_example C hC    obtain ⟨w,hw,hadj⟩ := hs 7 h7    refine ⟨w,hw,?_⟩    change ((7 : Fin 20).val < 7 ∧ (w.val = ((7 : Fin 20).val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨      ((7 : Fin 20).val = 7 ∧ w.val < 7) ∨      (8 ≤ (7 : Fin 20).val ∧ (7 : Fin 20).val < 13 ∧        (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < (7 : Fin 20).val) ∨ (13 ≤ w.val ∧ (7 : Fin 20).val + w.val < 27))) at hadj    omega  · exact ⟨0, in833_cut20_cycle_no_apex_core C hC hB h7 0 (by norm_num), by norm_num⟩private theorem in833_cut20_no_two :    let D := digraph_cut20_sharp_example    let B : Finset (Fin 20) := Finset.univ.filter fun v => v.val < 13    ¬ ∃ c : Fin 2 → Finset (Fin 20),      (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j)) := by  dsimp only  intro ⟨c,hc,hdis⟩  have hdis01 : Disjoint (c 0) (c 1) := hdis (by decide)  have hB (i : Fin 2) : ∀ v ∈ c i, v.val < 13 := by    intro v hv    have h := (hc i).1 hv    simpa using h  by_cases h70 : (7 : Fin 20) ∈ c 0  · by_cases h71 : (7 : Fin 20) ∈ c 1    · exact (Finset.disjoint_left.mp hdis01) h70 h71    · obtain ⟨v,hv,hv7⟩ := in833_cut20_cycle_has_core (c 0) (hc 0).2 (hB 0)      have hv' := in833_cut20_cycle_no_apex_core (c 1) (hc 1).2 (hB 1) h71 v hv7      exact (Finset.disjoint_left.mp hdis01) hv hv'  · obtain ⟨v,hv,hv7⟩ := in833_cut20_cycle_has_core (c 1) (hc 1).2 (hB 1)    have hv' := in833_cut20_cycle_no_apex_core (c 0) (hc 0).2 (hB 0) h70 v hv7    exact (Finset.disjoint_left.mp hdis01) hv' hvprivate theorem in833_cut20_robust :    let D := digraph_cut20_sharp_example    ∀ T : Finset (Fin 20), T.Nonempty →      (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) →      3 ≤ (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card := by  dsimp only  intro T hne hdeg  have hsink (v : Fin 20) (hv : v ∈ T) : v.val < 13 := by    by_contra h    have hfalse : ∀ w : Fin 20, ¬ digraph_cut20_sharp_example.Adj v w := by      intro w      change ¬ ((v.val < 7 ∧ (w.val = (v.val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨        (v.val = 7 ∧ w.val < 7) ∨        (8 ≤ v.val ∧ v.val < 13 ∧          (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < v.val) ∨ (13 ≤ w.val ∧ v.val + w.val < 27))))      omega    have he : T.filter (fun w => digraph_cut20_sharp_example.Adj v w) = ∅ := by      ext w      simp [hfalse w]    have hh := hdeg v hv    rw [he] at hh    simp at hh  have hbound (v : Fin 20) (hv : v ∈ T) : v.val < 8 := by    by_contra hh    let U := T.filter fun w => 8 ≤ w.val    have hU : U.Nonempty := ⟨v, Finset.mem_filter.mpr ⟨hv, by omega⟩⟩    let u := U.min' hU    have hu : u ∈ U := Finset.min'_mem U hU    have huT : u ∈ T := (Finset.mem_filter.mp hu).1    have hu8 : 8 ≤ u.val := (Finset.mem_filter.mp hu).2    have hu13 := hsink u huT    have hsub : T.filter (fun w => digraph_cut20_sharp_example.Adj u w) ⊆ {7} := by      intro w hw      have hwT : w ∈ T := (Finset.mem_filter.mp hw).1      have hadj := (Finset.mem_filter.mp hw).2      have hw13 := hsink w hwT      have hnot : ¬ (8 ≤ w.val ∧ w.val < u.val) := by        intro h        have hwU : w ∈ U := Finset.mem_filter.mpr ⟨hwT,h.1⟩        have hmin := Finset.min'_le U w hwU        have : u.val ≤ w.val := hmin        omega      have heq : w.val = 7 := by        change (u.val < 7 ∧ (w.val = (u.val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨          (u.val = 7 ∧ w.val < 7) ∨          (8 ≤ u.val ∧ u.val < 13 ∧            (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < u.val) ∨ (13 ≤ w.val ∧ u.val + w.val < 27))) at hadj        omega      have : w = (7 : Fin 20) := Fin.ext heq      simpa [this]    have hle := Finset.card_le_card hsub    simp only [Finset.card_singleton] at hle    have hge := hdeg u huT    omega  have hcard : 2 ≤ T.card := by    obtain ⟨v,hv⟩ := hne    have hh := hdeg v hv    have hsub := Finset.card_le_card (Finset.filter_subset (fun w => digraph_cut20_sharp_example.Adj v w) T)    omega  have hcore : ∃ v ∈ T, v.val < 7 := by    by_contra hh    push_neg at hh    have hsub : T ⊆ {7} := by      intro v hv      have h1 := hbound v hv      have h2 := hh v hv      have : v = (7 : Fin 20) := Fin.ext (by omega)      simpa [this]    have hle := Finset.card_le_card hsub    simp only [Finset.card_singleton] at hle    omega  have hstep (v : Fin 20) (hv : v ∈ T) (hv7 : v.val < 7) :      (7 : Fin 20) ∈ T ∧      (⟨(v.val + 1) % 7, by have := Nat.mod_lt (v.val+1) (by norm_num : 0 < 7); omega⟩ : Fin 20) ∈ T := by    let next : Fin 20 := ⟨(v.val+1)%7, by have := Nat.mod_lt (v.val+1) (by norm_num : 0 < 7); omega⟩    have hout : ∀ w ∈ T, digraph_cut20_sharp_example.Adj v w → w = 7 ∨ w = next := by      intro w hw hadj      have hw8 := hbound w hw      have hval : w.val = 7 ∨ w.val = (v.val+1)%7 := by        change (v.val < 7 ∧ (w.val = (v.val + 1) % 7 ∨ w.val = 7 ∨ (8 ≤ w.val ∧ w.val < 13))) ∨          (v.val = 7 ∧ w.val < 7) ∨          (8 ≤ v.val ∧ v.val < 13 ∧            (w.val = 7 ∨ (8 ≤ w.val ∧ w.val < v.val) ∨ (13 ≤ w.val ∧ v.val + w.val < 27))) at hadj        omega      rcases hval with h | h      · exact Or.inl (Fin.ext h)      · exact Or.inr (Fin.ext h)    have hfilter := hdeg v hv    constructor    · by_contra h7      have hsub : T.filter (fun w => digraph_cut20_sharp_example.Adj v w) ⊆ {next} := by        intro w hw        obtain ⟨hwT,hadj⟩ := Finset.mem_filter.mp hw        rcases hout w hwT hadj with heq | heq        · subst w; contradiction        · simpa [heq]      have hh := Finset.card_le_card hsub      simp only [Finset.card_singleton] at hh      omega    · by_contra hn      have hsub : T.filter (fun w => digraph_cut20_sharp_example.Adj v w) ⊆ {7} := by        intro w hw        obtain ⟨hwT,hadj⟩ := Finset.mem_filter.mp hw        rcases hout w hwT hadj with heq | heq        · simpa [heq]        · subst w; contradiction      have hh := Finset.card_le_card hsub      simp only [Finset.card_singleton] at hh      omega  have h0 : (0 : Fin 20) ∈ T := by    by_contra h0    have h6 : (6 : Fin 20) ∉ T := by      intro h      apply h0      simpa using (hstep 6 h (by norm_num)).2    have h5 : (5 : Fin 20) ∉ T := by      intro h      apply h6      simpa using (hstep 5 h (by norm_num)).2    have h4 : (4 : Fin 20) ∉ T := by      intro h      apply h5      simpa using (hstep 4 h (by norm_num)).2    have h3 : (3 : Fin 20) ∉ T := by      intro h      apply h4      simpa using (hstep 3 h (by norm_num)).2    have h2 : (2 : Fin 20) ∉ T := by      intro h      apply h3      simpa using (hstep 2 h (by norm_num)).2    have h1 : (1 : Fin 20) ∉ T := by      intro h      apply h2      simpa using (hstep 1 h (by norm_num)).2    obtain ⟨v,hv,hv7⟩ := hcore    fin_cases v <;> norm_num at hv7 <;>      first | exact h0 (by simpa using hv) | exact h1 (by simpa using hv) | exact h2 (by simpa using hv) | exact h3 (by simpa using hv) | exact h4 (by simpa using hv) | exact h5 (by simpa using hv) | exact h6 (by simpa using hv)  have h1 : (1 : Fin 20) ∈ T := by simpa using (hstep 0 h0 (by norm_num)).2  have h2 : (2 : Fin 20) ∈ T := by simpa using (hstep 1 h1 (by norm_num)).2  have h3 : (3 : Fin 20) ∈ T := by simpa using (hstep 2 h2 (by norm_num)).2  have h4 : (4 : Fin 20) ∈ T := by simpa using (hstep 3 h3 (by norm_num)).2  have h5 : (5 : Fin 20) ∈ T := by simpa using (hstep 4 h4 (by norm_num)).2  have h6 : (6 : Fin 20) ∈ T := by simpa using (hstep 5 h5 (by norm_num)).2  have h7 : (7 : Fin 20) ∈ T := (hstep 0 h0 (by norm_num)).1  have hT : T = Finset.univ.filter (fun v : Fin 20 => v.val < 8) := by    ext v    constructor    · intro hv      exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, hbound v hv⟩    · intro hv      have hv' := (Finset.mem_filter.mp hv).2      fin_cases v <;> norm_num at hv' <;>        first | simpa using h0 | simpa using h1 | simpa using h2 | simpa using h3 | simpa using h4 | simpa using h5 | simpa using h6 | simpa using h7  rw [hT]  decideprivate theorem in833_cut20_degree :    let D := digraph_cut20_sharp_example    let B : Finset (Fin 20) := Finset.univ.filter fun v => v.val < 13    ∀ v ∈ B, (Finset.univ.filter fun w => D.Adj v w).card = 7 := by  decideprivate theorem in833_cut20_boundary :    let D := digraph_cut20_sharp_example    let B : Finset (Fin 20) := Finset.univ.filter fun v => v.val < 13    (∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card) = 20 := by  decidetheorem digraph_cut20_sharp_example_certificate :    let D := digraph_cut20_sharp_example    let B : Finset (Fin 20) := Finset.univ.filter fun v => v.val < 13    (∀ v ∈ B, (Finset.univ.filter fun w => D.Adj v w).card = 7) ∧    (∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card) = 20 ∧    (¬ ∃ c : Fin 2 → Finset (Fin 20),      (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j))) ∧    (∀ T : Finset (Fin 20), T.Nonempty →      (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) →      3 ≤ (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card) := by  exact ⟨in833_cut20_degree, in833_cut20_boundary, in833_cut20_no_two, in833_cut20_robust⟩
See it in the graphDiscuss this resultChallenge it