AFTD Auto-Formalizing Theoretical Domains

digraph_oriented_cut20_sharp_example_certificate

theoremverified

The explicit oriented example has a seven-outregular twenty-vertex part with twenty outgoing arcs and no two disjoint cycles; every nonempty induced subset of minimum outdegree two has at least three vertices of outdegree two.

Statement

theorem digraph_oriented_cut20_sharp_example_certificate :
    let D := digraph_oriented_cut20_sharp_example
    let B : Finset (Fin 26) := Finset.univ.filter fun v => v.val < 20
    (∀ u v, D.Adj u v → ¬ D.Adj v u) ∧
    (∀ 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 26), (∀ i, digraph_directed_cycle_on D (c i)) ∧
      Pairwise (fun i j => Disjoint (c i) (c j))) ∧
    (∀ T : Finset (Fin 26), 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
Structural certificate for the construction in experiment 26321.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • digraph_oriented_cut20_sharp_exampleThe explicit oriented 26-vertex graph with five low vertices, a target, a directed seven-cycle, seven acyclic high vertices and six sinks.
  • 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 3

The proof, explained

The explicit 26-vertex oriented graph D has no outgoing arcs from the sink set {20, ..., 25}, so any sink-free subset T (such as a directed cycle or a subgraph of minimum outdegree at least 2) must lie in {0, ..., 19}. If T contains any low vertex (< 5), its minimal low vertex can only have vertex 5 as an out-neighbor in T. Consequently, any directed cycle avoiding 5 cannot contain any low vertex and must contain the entire 7-cycle P = {6, ..., 12}, while any other cycle must also hit P, proving no two disjoint cycles exist. Similarly, in any induced subgraph of minimum outdegree at least 2, every vertex of P must be present and can have at most two out-neighbors ({5} and its cycle successor), giving at least 7 (and thus at least 3) vertices of outdegree 2.

  1. The adjacency relation on the 26-vertex example digraph is decidable. automation

    The definition of adjacency consists of disjunctions of bounded linear inequalities and modular arithmetic on Fin 26, which Lean's typeclass synthesis automatically decides by unfolding the definition.

    lines 4–6

    private instance : DecidableRel digraph_oriented_cut20_sharp_example.Adj := by
      unfold digraph_oriented_cut20_sharp_example
      infer_instance
  2. The digraph is an oriented graph: it contains no 2-cycles (if u → v then not v → u). automation

    Lean's `decide` tactic checks all 26 × 26 pairs of vertices by finite computation to verify that adjacency is asymmetric.

    lines 8–11

    private theorem in833_oriented_cut20_orientation :
        ∀ u v, digraph_oriented_cut20_sharp_example.Adj u v → ¬ digraph_oriented_cut20_sharp_example.Adj v u := by
      decide
    
  3. Every vertex in B = {v ∈ Fin 26 | v < 20} has outdegree exactly 7 in the digraph. automation

    The `decide` tactic exhaustively computes the size of the out-neighborhood for each of the 20 vertices in B and checks that each cardinality is 7.

    lines 12–16

    private theorem in833_oriented_cut20_degree :
        ∀ v ∈ (Finset.univ.filter fun v : Fin 26 => v.val < 20),
          (Finset.univ.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card = 7 := by
      decide
    
  4. The number of arcs leaving B into its complement {20, ..., 25} is exactly 20. automation

    The `decide` tactic evaluates the sum of outgoing boundary degrees across all 20 vertices of B by finite computation, yielding 20.

    lines 17–21

    private theorem in833_oriented_cut20_boundary :
        (∑ v ∈ (Finset.univ.filter fun v : Fin 26 => v.val < 20),
          ((Finset.univ.filter fun v : Fin 26 => v.val < 20)ᶜ.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card) = 20 := by
      decide
    
  5. Any subset of vertices T with no sinks is entirely contained in {0, ..., 19}. automation

    By definition, no outgoing arcs originate from any vertex with value at least 20. Thus, any vertex in T must have an outgoing arc, which is impossible if its value is 20 or greater.

    lines 22–33

    private theorem in833_oriented_no_sinks
        (T : Finset (Fin 26))
        (hs : ∀ v ∈ T, ∃ w ∈ T, digraph_oriented_cut20_sharp_example.Adj v w) :
        ∀ v ∈ T, v.val < 20 := by
      intro v hv
      obtain ⟨w, hw, ha⟩ := hs v hv
      change (v.val < 5 ∧ (w.val < v.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ v.val + w.val < 26))) ∨
        (v.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨
        (6 ≤ v.val ∧ v.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (v.val - 6 + 1) % 7)) ∨
        (13 ≤ v.val ∧ v.val < 20 ∧ ((13 ≤ w.val ∧ w.val < v.val) ∨ (6 ≤ w.val ∧ v.val + w.val < 26))) at ha
      omega
    
  6. If a sink-free subset T contains any vertex less than 5, its minimal such vertex has no out-neighbors in T other than possibly vertex 5.

    Let v be the minimum of the nonempty set L = T ∩ {0, ..., 4}. In the graph, outgoing arcs from v go to w < v, w = 5, or w ≥ 20. Since T contains no vertices ≥ 20, and no vertex in T ∩ {0, ..., 4} can be smaller than the minimum v, the only candidate out-neighbor in T is 5.

    lines 34–66

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

    private theorem in833_oriented_low_witness
        (T : Finset (Fin 26))
        (hnosink : ∀ v ∈ T, v.val < 20)
        (hex : ∃ v ∈ T, v.val < 5) :
        ∃ v ∈ T, v.val < 5 ∧
          (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w) ⊆ {5} := by
      let L := T.filter fun v => v.val < 5
      have hL : L.Nonempty := by
        obtain ⟨v, hv, hv5⟩ := hex
        exact ⟨v, Finset.mem_filter.mpr ⟨hv, hv5⟩⟩
      let v := L.min' hL
      have hvL : v ∈ L := Finset.min'_mem L hL
      have hvT : v ∈ T := (Finset.mem_filter.mp hvL).1
      have hv5 : v.val < 5 := (Finset.mem_filter.mp hvL).2
      refine ⟨v, hvT, hv5, ?_⟩
      intro w hw
      obtain ⟨hwT, ha⟩ := Finset.mem_filter.mp hw
      have hw20 := hnosink w hwT
      have hmin : ∀ z ∈ L, v.val ≤ z.val := by
        intro z hz
        exact Finset.min'_le L z hz
      change (v.val < 5 ∧ (w.val < v.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ v.val + w.val < 26))) ∨
        (v.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨
        (6 ≤ v.val ∧ v.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (v.val - 6 + 1) % 7)) ∨
        (13 ≤ v.val ∧ v.val < 20 ∧ ((13 ≤ w.val ∧ w.val < v.val) ∨ (6 ≤ w.val ∧ v.val + w.val < 26))) at ha
      have hw5 : w.val = 5 := by
        by_contra hh
        have hwL : w ∈ L := Finset.mem_filter.mpr ⟨hwT, by omega⟩
        have hhmin := hmin w hwL
        omega
      simp only [Finset.mem_singleton]
      exact Fin.ext hw5
    
  7. Any nonempty sink-free subset T containing no vertices less than 5 must intersect {6, ..., 12}.

    Suppose for contradiction T is disjoint from {6, ..., 12}. If T contains a vertex ≥ 13, its minimal element in {13, ..., 19} cannot have out-neighbors in T because its arcs go only to smaller elements ≥ 13 or into {6, ..., 12}. If T has no vertex ≥ 13, then T = {5}, but vertex 5 only sends arcs to {13, ..., 19}, so 5 would be a sink in T.

    lines 67–106

    uses in833_oriented_no_sinks, Finset.mem_filter.mpr, Finset.min'_mem, Finset.mem_filter.mp, Finset.min'_le

    private theorem in833_oriented_has_parent
        (T : Finset (Fin 26)) (hne : T.Nonempty)
        (hs : ∀ v ∈ T, ∃ w ∈ T, digraph_oriented_cut20_sharp_example.Adj v w)
        (hlow : ∀ v ∈ T, ¬ v.val < 5) :
        ∃ p ∈ T, 6 ≤ p.val ∧ p.val < 13 := by
      have hnosink := in833_oriented_no_sinks T hs
      by_contra hn
      have hnoP : ∀ p ∈ T, ¬ (6 ≤ p.val ∧ p.val < 13) := by
        intro p hp hpP
        exact hn ⟨p, hp, hpP⟩
      have hR : (T.filter fun v => 13 ≤ v.val).Nonempty := by
        obtain ⟨v, hv⟩ := hne
        by_cases hvR : 13 ≤ v.val
        · exact ⟨v, Finset.mem_filter.mpr ⟨hv, hvR⟩⟩
        · have hvlow := hlow v hv
          have hvnosink := hnosink v hv
          have hvP := hnoP v hv
          have hvq : v.val = 5 := by omega
          obtain ⟨w, hw, ha⟩ := hs v hv
          change (v.val < 5 ∧ (w.val < v.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ v.val + w.val < 26))) ∨
            (v.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨
            (6 ≤ v.val ∧ v.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (v.val - 6 + 1) % 7)) ∨
            (13 ≤ v.val ∧ v.val < 20 ∧ ((13 ≤ w.val ∧ w.val < v.val) ∨ (6 ≤ w.val ∧ v.val + w.val < 26))) at ha
          exact ⟨w, Finset.mem_filter.mpr ⟨hw, by omega⟩⟩
      let R := T.filter fun v => 13 ≤ v.val
      let r := R.min' hR
      have hrR : r ∈ R := Finset.min'_mem R hR
      have hrT : r ∈ T := (Finset.mem_filter.mp hrR).1
      have hr13 : 13 ≤ r.val := (Finset.mem_filter.mp hrR).2
      have hr20 := hnosink r hrT
      obtain ⟨w, hwT, ha⟩ := hs r hrT
      have hnoPw := hnoP w hwT
      change (r.val < 5 ∧ (w.val < r.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ r.val + w.val < 26))) ∨
        (r.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨
        (6 ≤ r.val ∧ r.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (r.val - 6 + 1) % 7)) ∨
        (13 ≤ r.val ∧ r.val < 20 ∧ ((13 ≤ w.val ∧ w.val < r.val) ∨ (6 ≤ w.val ∧ r.val + w.val < 26))) at ha
      have hwR : w ∈ R := Finset.mem_filter.mpr ⟨hwT, by omega⟩
      have hwmin : r.val ≤ w.val := Finset.min'_le R w hwR
      omega
    
  8. Every directed cycle C is nonempty and every vertex in C has an out-neighbor in C.

    A cycle is represented as a list of at least two vertices where each vertex has an arc to the next, and the last has an arc to the head. Selecting the successor element in the list (or the head for the last element) provides an out-neighbor in C for every vertex.

    lines 107–137

    uses List.head?_cons, Option.some.injEq, List.mem_toFinset, List.getElem_of_mem, List.getElem_mem, List.getLast?_eq_getElem?, List.getElem?_eq_getElem

    private theorem in833_oriented_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 hclose
    
    
  9. For any p in {6, ..., 12}, if T contains no vertices less than 5, its out-neighbors in T are contained in {5, next(p)}.

    By the definition of adjacency, outgoing arcs from p ∈ {6, ..., 12} go only to vertices strictly less than 6 and to next(p) = 6 + (p - 6 + 1) % 7. Since T contains no vertices in {0, ..., 4}, the only remaining possible out-neighbors in T are 5 and next(p).

    lines 138–161

    uses Nat.mod_lt, Finset.mem_filter.mp, Finset.mem_insert, Finset.mem_singleton, Or.inl, Or.inr, Fin.ext

    private def in833_oriented_next (p : Fin 26) : Fin 26 :=
      ⟨6 + (p.val - 6 + 1) % 7, by have := Nat.mod_lt (p.val - 6 + 1) (by decide : 0 < 7); omega⟩
    
    private theorem in833_oriented_parent_neighbors
        (T : Finset (Fin 26))
        (hlow : ∀ v ∈ T, ¬ v.val < 5)
        (p : Fin 26) (hp6 : 6 ≤ p.val) (hp13 : p.val < 13) :
        (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj p w) ⊆ {5, in833_oriented_next p} := by
      intro w hw
      obtain ⟨hwT, ha⟩ := Finset.mem_filter.mp hw
      have hwlow := hlow w hwT
      change (p.val < 5 ∧ (w.val < p.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ p.val + w.val < 26))) ∨
        (p.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨
        (6 ≤ p.val ∧ p.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (p.val - 6 + 1) % 7)) ∨
        (13 ≤ p.val ∧ p.val < 20 ∧ ((13 ≤ w.val ∧ w.val < p.val) ∨ (6 ≤ w.val ∧ p.val + w.val < 26))) at ha
      have hval : w.val = 5 ∨ w.val = (in833_oriented_next p).val := by
        change w.val = 5 ∨ w.val = 6 + (p.val - 6 + 1) % 7
        omega
      simp only [Finset.mem_insert, Finset.mem_singleton]
      rcases hval with h | h
      · exact Or.inl (Fin.ext h)
      · exact Or.inr (Fin.ext h)
    
    private theorem in833_oriented_cycle_of_parents
  10. If a subset T intersects {6, ..., 12} and is closed under the cyclic successor next, it contains all 7 vertices of {6, ..., 12}. automation

    The cyclic shift next generates the full 7-cycle 6 → 7 → 8 → 9 → 10 → 11 → 12 → 6. Finite case exhaustion checks that if any one of these 7 vertices is in T, all 7 must belong to T.

    lines 162–198

        (T : Finset (Fin 26))
        (hstep : ∀ p ∈ T, 6 ≤ p.val → p.val < 13 → in833_oriented_next p ∈ T)
        (hex : ∃ p ∈ T, 6 ≤ p.val ∧ p.val < 13) :
        ∀ p : Fin 26, 6 ≤ p.val → p.val < 13 → p ∈ T := by
      have h67 : (6 : Fin 26) ∈ T → (7 : Fin 26) ∈ T := by
        intro h
        simpa [in833_oriented_next] using hstep 6 h (by decide) (by decide)
      have h78 : (7 : Fin 26) ∈ T → (8 : Fin 26) ∈ T := by
        intro h
        simpa [in833_oriented_next] using hstep 7 h (by decide) (by decide)
      have h89 : (8 : Fin 26) ∈ T → (9 : Fin 26) ∈ T := by
        intro h
        simpa [in833_oriented_next] using hstep 8 h (by decide) (by decide)
      have h910 : (9 : Fin 26) ∈ T → (10 : Fin 26) ∈ T := by
        intro h
        simpa [in833_oriented_next] using hstep 9 h (by decide) (by decide)
      have h1011 : (10 : Fin 26) ∈ T → (11 : Fin 26) ∈ T := by
        intro h
        simpa [in833_oriented_next] using hstep 10 h (by decide) (by decide)
      have h1112 : (11 : Fin 26) ∈ T → (12 : Fin 26) ∈ T := by
        intro h
        simpa [in833_oriented_next] using hstep 11 h (by decide) (by decide)
      have h126 : (12 : Fin 26) ∈ T → (6 : Fin 26) ∈ T := by
        intro h
        simpa [in833_oriented_next] using hstep 12 h (by decide) (by decide)
      obtain ⟨p, hp, hp6, hp13⟩ := hex
      have hp6T : (6 : Fin 26) ∈ T := by
        fin_cases p <;> (try norm_num at hp6) <;> (try norm_num at hp13) <;> aesop
      have hp7T := h67 hp6T
      have hp8T := h78 hp7T
      have hp9T := h89 hp8T
      have hp10T := h910 hp9T
      have hp11T := h1011 hp10T
      have hp12T := h1112 hp11T
      intro p hp6 hp13
      fin_cases p <;> (try norm_num at hp6) <;> (try norm_num at hp13) <;> assumption
    
  11. Every nonempty sink-free subset T must intersect the parent cycle {6, ..., 12}.

    If T were disjoint from {6, ..., 12}, the minimal element in T ∩ {13, ..., 19} would have no out-neighbor in T, so T cannot contain any vertex ≥ 13. Then vertex 5 cannot be in T since its out-arcs go only to {13, ..., 19}. Hence T ⊆ {0, ..., 4}. But the minimal element of T ∩ {0, ..., 4} can only have 5 as an out-neighbor, contradicting 5 ∉ T.

    lines 199–252

    uses in833_oriented_no_sinks, in833_oriented_low_witness, Finset.mem_filter.mpr, Finset.min'_mem, Finset.mem_filter.mp, Finset.min'_le, Fin.ext

    private theorem in833_oriented_every_successor_set_hits_parent
        (T : Finset (Fin 26)) (hne : T.Nonempty)
        (hs : ∀ v ∈ T, ∃ w ∈ T, digraph_oriented_cut20_sharp_example.Adj v w) :
        ∃ p ∈ T, 6 ≤ p.val ∧ p.val < 13 := by
      have hnosink := in833_oriented_no_sinks T hs
      by_contra hn
      have hnoP : ∀ p ∈ T, ¬ (6 ≤ p.val ∧ p.val < 13) := by
        intro p hp hpP
        exact hn ⟨p, hp, hpP⟩
      have hnoR : ∀ r ∈ T, ¬ 13 ≤ r.val := by
        intro r hr hrR
        let R := T.filter fun v => 13 ≤ v.val
        have hR : R.Nonempty := ⟨r, Finset.mem_filter.mpr ⟨hr, hrR⟩⟩
        let x := R.min' hR
        have hxR : x ∈ R := Finset.min'_mem R hR
        have hxT : x ∈ T := (Finset.mem_filter.mp hxR).1
        have hx13 : 13 ≤ x.val := (Finset.mem_filter.mp hxR).2
        have hx20 := hnosink x hxT
        obtain ⟨w, hwT, ha⟩ := hs x hxT
        have hnoPw := hnoP w hwT
        change (x.val < 5 ∧ (w.val < x.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ x.val + w.val < 26))) ∨
          (x.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨
          (6 ≤ x.val ∧ x.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (x.val - 6 + 1) % 7)) ∨
          (13 ≤ x.val ∧ x.val < 20 ∧ ((13 ≤ w.val ∧ w.val < x.val) ∨ (6 ≤ w.val ∧ x.val + w.val < 26))) at ha
        have hwR : w ∈ R := Finset.mem_filter.mpr ⟨hwT, by omega⟩
        have hwmin : x.val ≤ w.val := Finset.min'_le R w hwR
        omega
      have hq : (5 : Fin 26) ∉ T := by
        intro hqT
        obtain ⟨w, hw, ha⟩ := hs 5 hqT
        have hwnR := hnoR w hw
        change ((5 : Fin 26).val < 5 ∧ (w.val < (5 : Fin 26).val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ (5 : Fin 26).val + w.val < 26))) ∨
          ((5 : Fin 26).val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨
          (6 ≤ (5 : Fin 26).val ∧ (5 : Fin 26).val < 13 ∧ (w.val < 6 ∨ w.val = 6 + ((5 : Fin 26).val - 6 + 1) % 7)) ∨
          (13 ≤ (5 : Fin 26).val ∧ (5 : Fin 26).val < 20 ∧ ((13 ≤ w.val ∧ w.val < (5 : Fin 26).val) ∨ (6 ≤ w.val ∧ (5 : Fin 26).val + w.val < 26))) at ha
        omega
      have hlow : ∀ v ∈ T, ¬ v.val < 5 := by
        intro v hv hv5
        obtain ⟨x, hx, hx5, hsub⟩ := in833_oriented_low_witness T hnosink ⟨v, hv, hv5⟩
        obtain ⟨w, hwT, ha⟩ := hs x hx
        have hwq : w ∈ ({5} : Finset (Fin 26)) := hsub (Finset.mem_filter.mpr ⟨hwT, ha⟩)
        have : w = 5 := by simpa using hwq
        subst w
        exact hq hwT
      obtain ⟨v, hv⟩ := hne
      have hvlo := hlow v hv
      have hvP := hnoP v hv
      have hvR := hnoR v hv
      have hv20 := hnosink v hv
      have hvq : v.val = 5 := by omega
      apply hq
      have : v = 5 := Fin.ext hvq
      simpa [this] using hv
    
  12. Any sink-free subset T that avoids vertex 5 contains no vertices less than 5.

    If T contained any vertex less than 5, the minimal such vertex would have 5 as its only possible out-neighbor in T, contradicting the assumption that 5 is not in T.

    lines 253–266

    uses in833_oriented_no_sinks, in833_oriented_low_witness, Finset.mem_filter.mpr

    private theorem in833_oriented_low_free_of_avoid_target
        (T : Finset (Fin 26))
        (hs : ∀ v ∈ T, ∃ w ∈ T, digraph_oriented_cut20_sharp_example.Adj v w)
        (hq : (5 : Fin 26) ∉ T) :
        ∀ v ∈ T, ¬ v.val < 5 := by
      intro v hv hv5
      have hnosink := in833_oriented_no_sinks T hs
      obtain ⟨x, hx, hx5, hsub⟩ := in833_oriented_low_witness T hnosink ⟨v, hv, hv5⟩
      obtain ⟨w, hw, ha⟩ := hs x hx
      have hwq : w ∈ ({5} : Finset (Fin 26)) := hsub (Finset.mem_filter.mpr ⟨hw, ha⟩)
      have : w = 5 := by simpa using hwq
      subst w
      exact hq hw
    
  13. Any directed cycle C avoiding vertex 5 must contain all 7 vertices of {6, ..., 12}.

    Since 5 ∉ C, C contains no vertices less than 5. Each vertex p ∈ C ∩ {6, ..., 12} has out-neighbors in C restricted to {5, next(p)}, which forces next(p) ∈ C. Because every sink-free set hits {6, ..., 12}, C contains at least one such vertex, and by closure under next, it contains all 7 vertices of the cycle.

    lines 267–284

    uses in833_oriented_cycle_successor, in833_oriented_low_free_of_avoid_target, in833_oriented_every_successor_set_hits_parent, in833_oriented_cycle_of_parents, in833_oriented_parent_neighbors, Finset.mem_filter.mpr, Finset.mem_insert, Finset.mem_singleton, False.elim

    private theorem in833_oriented_cycle_avoids_target_contains_parents
        (C : Finset (Fin 26)) (hc : digraph_directed_cycle_on digraph_oriented_cut20_sharp_example C)
        (hq : (5 : Fin 26) ∉ C) :
        ∀ p : Fin 26, 6 ≤ p.val → p.val < 13 → p ∈ C := by
      obtain ⟨hne, hs⟩ := in833_oriented_cycle_successor digraph_oriented_cut20_sharp_example C hc
      have hlow := in833_oriented_low_free_of_avoid_target C hs hq
      have hex := in833_oriented_every_successor_set_hits_parent C hne hs
      apply in833_oriented_cycle_of_parents C _ hex
      intro p hp hp6 hp13
      obtain ⟨w, hw, ha⟩ := hs p hp
      have hm := in833_oriented_parent_neighbors C hlow p hp6 hp13
        (Finset.mem_filter.mpr ⟨hw, ha⟩)
      simp only [Finset.mem_insert, Finset.mem_singleton] at hm
      rcases hm with h | h
      · subst w
        exact False.elim (hq hw)
      · simpa [h] using hw
    
  14. The digraph contains no two vertex-disjoint directed cycles.

    Vertex 5 can belong to at most one of two disjoint cycles. The cycle that avoids vertex 5 must contain all 7 vertices of {6, ..., 12}. But the other cycle is also a nonempty sink-free set and must hit {6, ..., 12}, contradicting disjointness.

    lines 285–301

    uses Finset.disjoint_left.mp, in833_oriented_cycle_avoids_target_contains_parents, in833_oriented_cycle_successor, in833_oriented_every_successor_set_hits_parent

    private theorem in833_oriented_no_two :
        ¬ ∃ c : Fin 2 → Finset (Fin 26),
          (∀ i, digraph_directed_cycle_on digraph_oriented_cut20_sharp_example (c i)) ∧
          Pairwise (fun i j => Disjoint (c i) (c j)) := by
      rintro ⟨c, hc, hd⟩
      have hd01 : Disjoint (c 0) (c 1) := hd (by decide)
      by_cases hq : (5 : Fin 26) ∈ c 0
      · have hq1 : (5 : Fin 26) ∉ c 1 := (Finset.disjoint_left.mp hd01) hq
        have hall := in833_oriented_cycle_avoids_target_contains_parents (c 1) (hc 1) hq1
        obtain ⟨hne, hs⟩ := in833_oriented_cycle_successor digraph_oriented_cut20_sharp_example (c 0) (hc 0)
        obtain ⟨p, hp, hp6, hp13⟩ := in833_oriented_every_successor_set_hits_parent (c 0) hne hs
        exact (Finset.disjoint_left.mp hd01) hp (hall p hp6 hp13)
      · have hall := in833_oriented_cycle_avoids_target_contains_parents (c 0) (hc 0) hq
        obtain ⟨hne, hs⟩ := in833_oriented_cycle_successor digraph_oriented_cut20_sharp_example (c 1) (hc 1)
        obtain ⟨p, hp, hp6, hp13⟩ := in833_oriented_every_successor_set_hits_parent (c 1) hne hs
        exact (Finset.disjoint_left.mp hd01) (hall p hp6 hp13) hp
    
  15. Any nonempty induced subset T with minimum outdegree at least 2 contains at least 3 vertices of outdegree less than 3.

    No vertex less than 5 can be in T, as the minimal such vertex would have outdegree at most 1. Hence for each p ∈ T ∩ {6, ..., 12}, its out-neighbors in T lie in {5, next(p)}. Since the outdegree in T is at least 2, both 5 and next(p) must be in T, so T contains the entire 7-cycle {6, ..., 12}. Every vertex p in this 7-cycle has at most two out-neighbors in T, hence outdegree exactly 2 in T, providing 7 ≥ 3 such vertices.

    lines 302–348

    uses Finset.card_pos.mp, Finset.mem_filter.mp, Finset.mem_filter.mpr, in833_oriented_no_sinks, in833_oriented_low_witness, Finset.card_le_card, Finset.card_singleton, in833_oriented_every_successor_set_hits_parent, in833_oriented_parent_neighbors, Finset.mem_insert, Finset.mem_singleton, False.elim, in833_oriented_cycle_of_parents, Finset.card_le_two

    private theorem in833_oriented_robust
        (T : Finset (Fin 26)) (hne : T.Nonempty)
        (hmin : ∀ v ∈ T, 2 ≤ (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card) :
        3 ≤ (T.filter fun v => (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card < 3).card := by
      have hs : ∀ v ∈ T, ∃ w ∈ T, digraph_oriented_cut20_sharp_example.Adj v w := by
        intro v hv
        have hp : 0 < (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card := by have := hmin v hv; omega
        obtain ⟨w, hw⟩ := Finset.card_pos.mp hp
        exact ⟨w, (Finset.mem_filter.mp hw).1, (Finset.mem_filter.mp hw).2⟩
      have hnosink := in833_oriented_no_sinks T hs
      have hlow : ∀ v ∈ T, ¬ v.val < 5 := by
        intro v hv hv5
        obtain ⟨x, hx, hx5, hsub⟩ := in833_oriented_low_witness T hnosink ⟨v, hv, hv5⟩
        have hcard := Finset.card_le_card hsub
        have hminx := hmin x hx
        simp only [Finset.card_singleton] at hcard
        omega
      have hex := in833_oriented_every_successor_set_hits_parent T hne hs
      have hstep : ∀ p ∈ T, 6 ≤ p.val → p.val < 13 → in833_oriented_next p ∈ T := by
        intro p hp hp6 hp13
        by_contra hn
        have hsub : (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj p w) ⊆ ({5} : Finset (Fin 26)) := by
          intro w hw
          have hpairs := in833_oriented_parent_neighbors T hlow p hp6 hp13 hw
          simp only [Finset.mem_insert, Finset.mem_singleton] at hpairs
          rcases hpairs with h | h
          · simpa using h
          · have hwT := (Finset.mem_filter.mp hw).1
            exact False.elim (hn (by simpa [h] using hwT))
        have hcard := Finset.card_le_card hsub
        have hminp := hmin p hp
        simp only [Finset.card_singleton] at hcard
        omega
      have hall := in833_oriented_cycle_of_parents T hstep hex
      let P : Finset (Fin 26) := Finset.univ.filter fun p => 6 ≤ p.val ∧ p.val < 13
      have hP : P ⊆ T.filter fun v => (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card < 3 := by
        intro p hp
        have hpval := (Finset.mem_filter.mp hp).2
        have hpT := hall p hpval.1 hpval.2
        have hsub := in833_oriented_parent_neighbors T hlow p hpval.1 hpval.2
        have hcard := Finset.card_le_card hsub
        have hpair : ({5, in833_oriented_next p} : Finset (Fin 26)).card ≤ 2 := Finset.card_le_two
        exact Finset.mem_filter.mpr ⟨hpT, by omega⟩
      have hPcard : P.card = 7 := by decide
      have hle := Finset.card_le_card hP
      omega
    
  16. The digraph satisfies the full certificate: orientation, 7-outregularity on B, boundary cut 20, no two disjoint cycles, and the robust outdegree property.

    The theorem combines the five previously proved lemmas into a single conjunction.

    lines 349–361

    uses in833_oriented_cut20_orientation, in833_oriented_cut20_degree, in833_oriented_cut20_boundary, in833_oriented_no_two, in833_oriented_robust

    theorem digraph_oriented_cut20_sharp_example_certificate :
        let D := digraph_oriented_cut20_sharp_example
        let B : Finset (Fin 26) := Finset.univ.filter fun v => v.val < 20
        (∀ u v, D.Adj u v → ¬ D.Adj v u) ∧
        (∀ 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 26), (∀ i, digraph_directed_cycle_on D (c i)) ∧
          Pairwise (fun i j => Disjoint (c i) (c j))) ∧
        (∀ T : Finset (Fin 26), 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_oriented_cut20_orientation, in833_oriented_cut20_degree,
        in833_oriented_cut20_boundary, in833_oriented_no_two, in833_oriented_robust⟩
False.elim
From False, any proposition follows.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.card_le_two
A pair finset {a, b} has cardinality at most 2.
Finset.card_le_card
If a finset s is a subset of t, the cardinality of s is at most that of t.
Finset.card_pos.mp
A finset has positive cardinality if and only if it contains at least one element.
Finset.card_singleton
The cardinality of any singleton finset is 1.
Finset.disjoint_left.mp
If two finsets are disjoint, an element in the first cannot belong to the second.
Finset.mem_filter.mp
An element is in Finset.filter p s if and only if it is in s and satisfies p (left-to-right direction).
Finset.mem_filter.mpr
An element is in Finset.filter p s if it is in s and satisfies p (right-to-left direction).
Finset.mem_insert
An element belongs to insert a s if and only if it equals a or belongs to s.
Finset.mem_singleton
An element belongs to {a} if and only if it equals a.
Finset.min'_le
The minimum element of a linearly ordered finset is less than or equal to any member.
Finset.min'_mem
The minimum element of a nonempty linearly ordered finset belongs to that finset.
List.head?_cons
The head of a cons list x :: xs is x.
List.getElem_mem
The element of a list at any valid index belongs to the list.
List.getElem_of_mem
Any member of a list appears at some valid index in the list.
List.getElem?_eq_getElem
Optional index lookup at a valid index returns some value of that index.
List.getLast?_eq_getElem?
The last element of a list is the element at index length - 1.
List.mem_toFinset
An element belongs to the finset of a list if and only if it belongs to the list.
Nat.mod_lt
For any positive divisor y, the remainder x % y is strictly less than y.
Option.some.injEq
Two Option.some values are equal if and only if their wrapped values are equal.
Or.inl
Derives a disjunction A ∨ B from the left disjunct A.
Or.inr
Derives a disjunction A ∨ B from the right disjunct B.
in833_oriented_cut20_boundary
The sum of outgoing arcs from B = {0, ..., 19} to Bᶜ = {20, ..., 25} is exactly 20.
in833_oriented_cut20_degree
Every vertex in {0, ..., 19} has outdegree 7 in the example digraph.
in833_oriented_cut20_orientation
The adjacency relation is an orientation (no two vertices have mutual arcs).
in833_oriented_cycle_avoids_target_contains_parents
Any directed cycle avoiding vertex 5 must contain all 7 vertices of the cycle {6, ..., 12}.
in833_oriented_cycle_of_parents
If a subset T intersects {6, ..., 12} and contains the cycle successor of each of its elements in that set, then T contains all of {6, ..., 12}.
in833_oriented_cycle_successor
Every directed cycle has a nonempty vertex set, and each of its vertices has an out-neighbor in the cycle.
in833_oriented_every_successor_set_hits_parent
Every nonempty sink-free subset of vertices intersects {6, ..., 12}.
in833_oriented_low_free_of_avoid_target
Any sink-free subset avoiding vertex 5 cannot contain any vertex strictly less than 5.
in833_oriented_low_witness
If a sink-free subset contains a vertex less than 5, its minimal such vertex has out-neighbors in T restricted to {5}.
in833_oriented_no_sinks
Any sink-free subset of vertices must be contained in {0, ..., 19}.
in833_oriented_no_two
The example digraph contains no two vertex-disjoint directed cycles.
in833_oriented_parent_neighbors
For any vertex p in {6, ..., 12}, its out-neighbors in a subset T containing no vertices less than 5 can only be 5 or next(p).
in833_oriented_robust
Any nonempty induced subgraph with minimum outdegree at least 2 has at least 3 vertices of outdegree less than 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 481 tactics.

set_option maxHeartbeats 5000000set_option maxRecDepth 4096private instance : DecidableRel digraph_oriented_cut20_sharp_example.Adj := by  unfold digraph_oriented_cut20_sharp_example  infer_instanceprivate theorem in833_oriented_cut20_orientation :    ∀ u v, digraph_oriented_cut20_sharp_example.Adj u v → ¬ digraph_oriented_cut20_sharp_example.Adj v u := by  decideprivate theorem in833_oriented_cut20_degree :    ∀ v ∈ (Finset.univ.filter fun v : Fin 26 => v.val < 20),      (Finset.univ.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card = 7 := by  decideprivate theorem in833_oriented_cut20_boundary :    (∑ v ∈ (Finset.univ.filter fun v : Fin 26 => v.val < 20),      ((Finset.univ.filter fun v : Fin 26 => v.val < 20)ᶜ.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card) = 20 := by  decideprivate theorem in833_oriented_no_sinks    (T : Finset (Fin 26))    (hs : ∀ v ∈ T, ∃ w ∈ T, digraph_oriented_cut20_sharp_example.Adj v w) :    ∀ v ∈ T, v.val < 20 := by  intro v hv  obtain ⟨w, hw, ha⟩ := hs v hv  change (v.val < 5 ∧ (w.val < v.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ v.val + w.val < 26))) ∨    (v.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨    (6 ≤ v.val ∧ v.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (v.val - 6 + 1) % 7)) ∨    (13 ≤ v.val ∧ v.val < 20 ∧ ((13 ≤ w.val ∧ w.val < v.val) ∨ (6 ≤ w.val ∧ v.val + w.val < 26))) at ha  omegaprivate theorem in833_oriented_low_witness    (T : Finset (Fin 26))    (hnosink : ∀ v ∈ T, v.val < 20)    (hex : ∃ v ∈ T, v.val < 5) :    ∃ v ∈ T, v.val < 5 ∧      (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w) ⊆ {5} := by  let L := T.filter fun v => v.val < 5  have hL : L.Nonempty := by    obtain ⟨v, hv, hv5⟩ := hex    exact ⟨v, Finset.mem_filter.mpr ⟨hv, hv5⟩⟩  let v := L.min' hL  have hvL : v ∈ L := Finset.min'_mem L hL  have hvT : v ∈ T := (Finset.mem_filter.mp hvL).1  have hv5 : v.val < 5 := (Finset.mem_filter.mp hvL).2  refine ⟨v, hvT, hv5, ?_⟩  intro w hw  obtain ⟨hwT, ha⟩ := Finset.mem_filter.mp hw  have hw20 := hnosink w hwT  have hmin : ∀ z ∈ L, v.val ≤ z.val := by    intro z hz    exact Finset.min'_le L z hz  change (v.val < 5 ∧ (w.val < v.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ v.val + w.val < 26))) ∨    (v.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨    (6 ≤ v.val ∧ v.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (v.val - 6 + 1) % 7)) ∨    (13 ≤ v.val ∧ v.val < 20 ∧ ((13 ≤ w.val ∧ w.val < v.val) ∨ (6 ≤ w.val ∧ v.val + w.val < 26))) at ha  have hw5 : w.val = 5 := by    by_contra hh    have hwL : w ∈ L := Finset.mem_filter.mpr ⟨hwT, by omega⟩    have hhmin := hmin w hwL    omega  simp only [Finset.mem_singleton]  exact Fin.ext hw5private theorem in833_oriented_has_parent    (T : Finset (Fin 26)) (hne : T.Nonempty)    (hs : ∀ v ∈ T, ∃ w ∈ T, digraph_oriented_cut20_sharp_example.Adj v w)    (hlow : ∀ v ∈ T, ¬ v.val < 5) :    ∃ p ∈ T, 6 ≤ p.val ∧ p.val < 13 := by  have hnosink := in833_oriented_no_sinks T hs  by_contra hn  have hnoP : ∀ p ∈ T, ¬ (6 ≤ p.val ∧ p.val < 13) := by    intro p hp hpP    exact hn ⟨p, hp, hpP⟩  have hR : (T.filter fun v => 13 ≤ v.val).Nonempty := by    obtain ⟨v, hv⟩ := hne    by_cases hvR : 13 ≤ v.val    · exact ⟨v, Finset.mem_filter.mpr ⟨hv, hvR⟩⟩    · have hvlow := hlow v hv      have hvnosink := hnosink v hv      have hvP := hnoP v hv      have hvq : v.val = 5 := by omega      obtain ⟨w, hw, ha⟩ := hs v hv      change (v.val < 5 ∧ (w.val < v.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ v.val + w.val < 26))) ∨        (v.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨        (6 ≤ v.val ∧ v.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (v.val - 6 + 1) % 7)) ∨        (13 ≤ v.val ∧ v.val < 20 ∧ ((13 ≤ w.val ∧ w.val < v.val) ∨ (6 ≤ w.val ∧ v.val + w.val < 26))) at ha      exact ⟨w, Finset.mem_filter.mpr ⟨hw, by omega⟩⟩  let R := T.filter fun v => 13 ≤ v.val  let r := R.min' hR  have hrR : r ∈ R := Finset.min'_mem R hR  have hrT : r ∈ T := (Finset.mem_filter.mp hrR).1  have hr13 : 13 ≤ r.val := (Finset.mem_filter.mp hrR).2  have hr20 := hnosink r hrT  obtain ⟨w, hwT, ha⟩ := hs r hrT  have hnoPw := hnoP w hwT  change (r.val < 5 ∧ (w.val < r.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ r.val + w.val < 26))) ∨    (r.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨    (6 ≤ r.val ∧ r.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (r.val - 6 + 1) % 7)) ∨    (13 ≤ r.val ∧ r.val < 20 ∧ ((13 ≤ w.val ∧ w.val < r.val) ∨ (6 ≤ w.val ∧ r.val + w.val < 26))) at ha  have hwR : w ∈ R := Finset.mem_filter.mpr ⟨hwT, by omega⟩  have hwmin : r.val ≤ w.val := Finset.min'_le R w hwR  omegaprivate theorem in833_oriented_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 def in833_oriented_next (p : Fin 26) : Fin 26 :=  ⟨6 + (p.val - 6 + 1) % 7, by have := Nat.mod_lt (p.val - 6 + 1) (by decide : 0 < 7); omega⟩private theorem in833_oriented_parent_neighbors    (T : Finset (Fin 26))    (hlow : ∀ v ∈ T, ¬ v.val < 5)    (p : Fin 26) (hp6 : 6 ≤ p.val) (hp13 : p.val < 13) :    (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj p w) ⊆ {5, in833_oriented_next p} := by  intro w hw  obtain ⟨hwT, ha⟩ := Finset.mem_filter.mp hw  have hwlow := hlow w hwT  change (p.val < 5 ∧ (w.val < p.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ p.val + w.val < 26))) ∨    (p.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨    (6 ≤ p.val ∧ p.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (p.val - 6 + 1) % 7)) ∨    (13 ≤ p.val ∧ p.val < 20 ∧ ((13 ≤ w.val ∧ w.val < p.val) ∨ (6 ≤ w.val ∧ p.val + w.val < 26))) at ha  have hval : w.val = 5 ∨ w.val = (in833_oriented_next p).val := by    change w.val = 5 ∨ w.val = 6 + (p.val - 6 + 1) % 7    omega  simp only [Finset.mem_insert, Finset.mem_singleton]  rcases hval with h | h  · exact Or.inl (Fin.ext h)  · exact Or.inr (Fin.ext h)private theorem in833_oriented_cycle_of_parents    (T : Finset (Fin 26))    (hstep : ∀ p ∈ T, 6 ≤ p.val → p.val < 13 → in833_oriented_next p ∈ T)    (hex : ∃ p ∈ T, 6 ≤ p.val ∧ p.val < 13) :    ∀ p : Fin 26, 6 ≤ p.val → p.val < 13 → p ∈ T := by  have h67 : (6 : Fin 26) ∈ T → (7 : Fin 26) ∈ T := by    intro h    simpa [in833_oriented_next] using hstep 6 h (by decide) (by decide)  have h78 : (7 : Fin 26) ∈ T → (8 : Fin 26) ∈ T := by    intro h    simpa [in833_oriented_next] using hstep 7 h (by decide) (by decide)  have h89 : (8 : Fin 26) ∈ T → (9 : Fin 26) ∈ T := by    intro h    simpa [in833_oriented_next] using hstep 8 h (by decide) (by decide)  have h910 : (9 : Fin 26) ∈ T → (10 : Fin 26) ∈ T := by    intro h    simpa [in833_oriented_next] using hstep 9 h (by decide) (by decide)  have h1011 : (10 : Fin 26) ∈ T → (11 : Fin 26) ∈ T := by    intro h    simpa [in833_oriented_next] using hstep 10 h (by decide) (by decide)  have h1112 : (11 : Fin 26) ∈ T → (12 : Fin 26) ∈ T := by    intro h    simpa [in833_oriented_next] using hstep 11 h (by decide) (by decide)  have h126 : (12 : Fin 26) ∈ T → (6 : Fin 26) ∈ T := by    intro h    simpa [in833_oriented_next] using hstep 12 h (by decide) (by decide)  obtain ⟨p, hp, hp6, hp13⟩ := hex  have hp6T : (6 : Fin 26) ∈ T := by    fin_cases p <;> (try norm_num at hp6) <;> (try norm_num at hp13) <;> aesop  have hp7T := h67 hp6T  have hp8T := h78 hp7T  have hp9T := h89 hp8T  have hp10T := h910 hp9T  have hp11T := h1011 hp10T  have hp12T := h1112 hp11T  intro p hp6 hp13  fin_cases p <;> (try norm_num at hp6) <;> (try norm_num at hp13) <;> assumptionprivate theorem in833_oriented_every_successor_set_hits_parent    (T : Finset (Fin 26)) (hne : T.Nonempty)    (hs : ∀ v ∈ T, ∃ w ∈ T, digraph_oriented_cut20_sharp_example.Adj v w) :    ∃ p ∈ T, 6 ≤ p.val ∧ p.val < 13 := by  have hnosink := in833_oriented_no_sinks T hs  by_contra hn  have hnoP : ∀ p ∈ T, ¬ (6 ≤ p.val ∧ p.val < 13) := by    intro p hp hpP    exact hn ⟨p, hp, hpP⟩  have hnoR : ∀ r ∈ T, ¬ 13 ≤ r.val := by    intro r hr hrR    let R := T.filter fun v => 13 ≤ v.val    have hR : R.Nonempty := ⟨r, Finset.mem_filter.mpr ⟨hr, hrR⟩⟩    let x := R.min' hR    have hxR : x ∈ R := Finset.min'_mem R hR    have hxT : x ∈ T := (Finset.mem_filter.mp hxR).1    have hx13 : 13 ≤ x.val := (Finset.mem_filter.mp hxR).2    have hx20 := hnosink x hxT    obtain ⟨w, hwT, ha⟩ := hs x hxT    have hnoPw := hnoP w hwT    change (x.val < 5 ∧ (w.val < x.val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ x.val + w.val < 26))) ∨      (x.val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨      (6 ≤ x.val ∧ x.val < 13 ∧ (w.val < 6 ∨ w.val = 6 + (x.val - 6 + 1) % 7)) ∨      (13 ≤ x.val ∧ x.val < 20 ∧ ((13 ≤ w.val ∧ w.val < x.val) ∨ (6 ≤ w.val ∧ x.val + w.val < 26))) at ha    have hwR : w ∈ R := Finset.mem_filter.mpr ⟨hwT, by omega⟩    have hwmin : x.val ≤ w.val := Finset.min'_le R w hwR    omega  have hq : (5 : Fin 26) ∉ T := by    intro hqT    obtain ⟨w, hw, ha⟩ := hs 5 hqT    have hwnR := hnoR w hw    change ((5 : Fin 26).val < 5 ∧ (w.val < (5 : Fin 26).val ∨ w.val = 5 ∨ (20 ≤ w.val ∧ (5 : Fin 26).val + w.val < 26))) ∨      ((5 : Fin 26).val = 5 ∧ 13 ≤ w.val ∧ w.val < 20) ∨      (6 ≤ (5 : Fin 26).val ∧ (5 : Fin 26).val < 13 ∧ (w.val < 6 ∨ w.val = 6 + ((5 : Fin 26).val - 6 + 1) % 7)) ∨      (13 ≤ (5 : Fin 26).val ∧ (5 : Fin 26).val < 20 ∧ ((13 ≤ w.val ∧ w.val < (5 : Fin 26).val) ∨ (6 ≤ w.val ∧ (5 : Fin 26).val + w.val < 26))) at ha    omega  have hlow : ∀ v ∈ T, ¬ v.val < 5 := by    intro v hv hv5    obtain ⟨x, hx, hx5, hsub⟩ := in833_oriented_low_witness T hnosink ⟨v, hv, hv5⟩    obtain ⟨w, hwT, ha⟩ := hs x hx    have hwq : w ∈ ({5} : Finset (Fin 26)) := hsub (Finset.mem_filter.mpr ⟨hwT, ha⟩)    have : w = 5 := by simpa using hwq    subst w    exact hq hwT  obtain ⟨v, hv⟩ := hne  have hvlo := hlow v hv  have hvP := hnoP v hv  have hvR := hnoR v hv  have hv20 := hnosink v hv  have hvq : v.val = 5 := by omega  apply hq  have : v = 5 := Fin.ext hvq  simpa [this] using hvprivate theorem in833_oriented_low_free_of_avoid_target    (T : Finset (Fin 26))    (hs : ∀ v ∈ T, ∃ w ∈ T, digraph_oriented_cut20_sharp_example.Adj v w)    (hq : (5 : Fin 26) ∉ T) :    ∀ v ∈ T, ¬ v.val < 5 := by  intro v hv hv5  have hnosink := in833_oriented_no_sinks T hs  obtain ⟨x, hx, hx5, hsub⟩ := in833_oriented_low_witness T hnosink ⟨v, hv, hv5⟩  obtain ⟨w, hw, ha⟩ := hs x hx  have hwq : w ∈ ({5} : Finset (Fin 26)) := hsub (Finset.mem_filter.mpr ⟨hw, ha⟩)  have : w = 5 := by simpa using hwq  subst w  exact hq hwprivate theorem in833_oriented_cycle_avoids_target_contains_parents    (C : Finset (Fin 26)) (hc : digraph_directed_cycle_on digraph_oriented_cut20_sharp_example C)    (hq : (5 : Fin 26) ∉ C) :    ∀ p : Fin 26, 6 ≤ p.val → p.val < 13 → p ∈ C := by  obtain ⟨hne, hs⟩ := in833_oriented_cycle_successor digraph_oriented_cut20_sharp_example C hc  have hlow := in833_oriented_low_free_of_avoid_target C hs hq  have hex := in833_oriented_every_successor_set_hits_parent C hne hs  apply in833_oriented_cycle_of_parents C _ hex  intro p hp hp6 hp13  obtain ⟨w, hw, ha⟩ := hs p hp  have hm := in833_oriented_parent_neighbors C hlow p hp6 hp13    (Finset.mem_filter.mpr ⟨hw, ha⟩)  simp only [Finset.mem_insert, Finset.mem_singleton] at hm  rcases hm with h | h  · subst w    exact False.elim (hq hw)  · simpa [h] using hwprivate theorem in833_oriented_no_two :    ¬ ∃ c : Fin 2 → Finset (Fin 26),      (∀ i, digraph_directed_cycle_on digraph_oriented_cut20_sharp_example (c i)) ∧      Pairwise (fun i j => Disjoint (c i) (c j)) := by  rintro ⟨c, hc, hd⟩  have hd01 : Disjoint (c 0) (c 1) := hd (by decide)  by_cases hq : (5 : Fin 26) ∈ c 0  · have hq1 : (5 : Fin 26) ∉ c 1 := (Finset.disjoint_left.mp hd01) hq    have hall := in833_oriented_cycle_avoids_target_contains_parents (c 1) (hc 1) hq1    obtain ⟨hne, hs⟩ := in833_oriented_cycle_successor digraph_oriented_cut20_sharp_example (c 0) (hc 0)    obtain ⟨p, hp, hp6, hp13⟩ := in833_oriented_every_successor_set_hits_parent (c 0) hne hs    exact (Finset.disjoint_left.mp hd01) hp (hall p hp6 hp13)  · have hall := in833_oriented_cycle_avoids_target_contains_parents (c 0) (hc 0) hq    obtain ⟨hne, hs⟩ := in833_oriented_cycle_successor digraph_oriented_cut20_sharp_example (c 1) (hc 1)    obtain ⟨p, hp, hp6, hp13⟩ := in833_oriented_every_successor_set_hits_parent (c 1) hne hs    exact (Finset.disjoint_left.mp hd01) (hall p hp6 hp13) hpprivate theorem in833_oriented_robust    (T : Finset (Fin 26)) (hne : T.Nonempty)    (hmin : ∀ v ∈ T, 2 ≤ (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card) :    3 ≤ (T.filter fun v => (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card < 3).card := by  have hs : ∀ v ∈ T, ∃ w ∈ T, digraph_oriented_cut20_sharp_example.Adj v w := by    intro v hv    have hp : 0 < (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card := by have := hmin v hv; omega    obtain ⟨w, hw⟩ := Finset.card_pos.mp hp    exact ⟨w, (Finset.mem_filter.mp hw).1, (Finset.mem_filter.mp hw).2⟩  have hnosink := in833_oriented_no_sinks T hs  have hlow : ∀ v ∈ T, ¬ v.val < 5 := by    intro v hv hv5    obtain ⟨x, hx, hx5, hsub⟩ := in833_oriented_low_witness T hnosink ⟨v, hv, hv5⟩    have hcard := Finset.card_le_card hsub    have hminx := hmin x hx    simp only [Finset.card_singleton] at hcard    omega  have hex := in833_oriented_every_successor_set_hits_parent T hne hs  have hstep : ∀ p ∈ T, 6 ≤ p.val → p.val < 13 → in833_oriented_next p ∈ T := by    intro p hp hp6 hp13    by_contra hn    have hsub : (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj p w) ⊆ ({5} : Finset (Fin 26)) := by      intro w hw      have hpairs := in833_oriented_parent_neighbors T hlow p hp6 hp13 hw      simp only [Finset.mem_insert, Finset.mem_singleton] at hpairs      rcases hpairs with h | h      · simpa using h      · have hwT := (Finset.mem_filter.mp hw).1        exact False.elim (hn (by simpa [h] using hwT))    have hcard := Finset.card_le_card hsub    have hminp := hmin p hp    simp only [Finset.card_singleton] at hcard    omega  have hall := in833_oriented_cycle_of_parents T hstep hex  let P : Finset (Fin 26) := Finset.univ.filter fun p => 6 ≤ p.val ∧ p.val < 13  have hP : P ⊆ T.filter fun v => (T.filter fun w => digraph_oriented_cut20_sharp_example.Adj v w).card < 3 := by    intro p hp    have hpval := (Finset.mem_filter.mp hp).2    have hpT := hall p hpval.1 hpval.2    have hsub := in833_oriented_parent_neighbors T hlow p hpval.1 hpval.2    have hcard := Finset.card_le_card hsub    have hpair : ({5, in833_oriented_next p} : Finset (Fin 26)).card ≤ 2 := Finset.card_le_two    exact Finset.mem_filter.mpr ⟨hpT, by omega⟩  have hPcard : P.card = 7 := by decide  have hle := Finset.card_le_card hP  omegatheorem digraph_oriented_cut20_sharp_example_certificate :    let D := digraph_oriented_cut20_sharp_example    let B : Finset (Fin 26) := Finset.univ.filter fun v => v.val < 20    (∀ u v, D.Adj u v → ¬ D.Adj v u) ∧    (∀ 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 26), (∀ i, digraph_directed_cycle_on D (c i)) ∧      Pairwise (fun i j => Disjoint (c i) (c j))) ∧    (∀ T : Finset (Fin 26), 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_oriented_cut20_orientation, in833_oriented_cut20_degree,    in833_oriented_cut20_boundary, in833_oriented_no_two, in833_oriented_robust⟩
See it in the graphDiscuss this resultChallenge it