digraph_cut20_sharp_example_certificate
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
- digraph_robust_cut_twenty_one_counterexampleLet D be digraph_cut20_sharp_example on Fin 20 and let B be the vertices with value below 13. The set B has at least seven vertices, each…
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.
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.
unfold digraph_cut20_sharp_example infer_instance
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.
uses
List.head?_cons,Option.some.injEq,List.mem_toFinsetobtain ⟨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⟩, ?_⟩
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.
uses
List.mem_toFinset,List.getElem_of_mem,List.getElem_mem,List.getLast?_eq_getElem?,List.getElem?_eq_getElemintro 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
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.
uses
in833_cycle_successor,Fin.ext,False.elimobtain ⟨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))
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.
uses
Nat.mod_lt,Fin.exthave 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
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.
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
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.
uses
in833_cycle_successor,in833_cut20_cycle_no_apex_coreby_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⟩
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.
uses
Finset.disjoint_left.mp,in833_cut20_cycle_has_core,in833_cut20_cycle_no_apex_coredsimp 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
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.
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
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.
uses
Finset.mem_filter.mpr,Finset.min'_mem,Finset.mem_filter.mp,Finset.min'_le,Fin.ext,Finset.card_le_card,Finset.card_singletonby_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
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.
uses
Finset.card_le_card,Finset.filter_subset,Fin.ext,Finset.card_singletonobtain ⟨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
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.
uses
Nat.mod_lt,Or.inl,Or.inr,Fin.ext,Finset.mem_filter.mp,Finset.card_le_card,Finset.card_singletonhave 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
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}.
uses
Finset.mem_filter.mpr,Finset.mem_univ,Finset.mem_filter.mpintro 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
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.
rw [hT] decide
Every vertex in B = {0, ..., 12} has outdegree exactly 7. automation
Verified directly by finite enumeration over all 13 vertices of B using decide.
decideExactly 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.
decideThe 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.
uses
in833_cut20_degree,in833_cut20_boundary,in833_cut20_no_two,in833_cut20_robustexact ⟨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.
- Several finite-graph verification steps (the outdegree regularity of B, the cut size of 20, and the internal outdegree check on the 8-vertex subgraph) are discharged directly by Lean's `decide` kernel evaluation rather than argued symbolically.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩