digraph_oriented_cut20_sharp_example_certificate
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
- digraph_oriented_regular_cut20_extension_certificateThe extended example is oriented, seven-outregular, arc-dominated and strongly connected, with a twenty-vertex part of cut twenty and no…
- digraph_oriented_robust_cut_twenty_one_counterexampleLet D be digraph_oriented_cut20_sharp_example on Fin 26 and B the set of vertices with value less than 20. D is oriented; B has at least…
- digraph_oriented_cut20_dominated_extension_certificateThe extended example is oriented, strongly connected, has minimum outdegree seven, a seven-outregular twenty-vertex part with cut twenty…
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.
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.
private instance : DecidableRel digraph_oriented_cut20_sharp_example.Adj := by unfold digraph_oriented_cut20_sharp_example infer_instance
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.
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
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.
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
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.
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
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.
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
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.
uses
Finset.mem_filter.mpr,Finset.min'_mem,Finset.mem_filter.mp,Finset.min'_le,Finset.mem_singleton,Fin.extprivate 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
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.
uses
in833_oriented_no_sinks,Finset.mem_filter.mpr,Finset.min'_mem,Finset.mem_filter.mp,Finset.min'_leprivate 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
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.
uses
List.head?_cons,Option.some.injEq,List.mem_toFinset,List.getElem_of_mem,List.getElem_mem,List.getLast?_eq_getElem?,List.getElem?_eq_getElemprivate 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
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).
uses
Nat.mod_lt,Finset.mem_filter.mp,Finset.mem_insert,Finset.mem_singleton,Or.inl,Or.inr,Fin.extprivate 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
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.
(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) <;> assumptionEvery 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.
uses
in833_oriented_no_sinks,in833_oriented_low_witness,Finset.mem_filter.mpr,Finset.min'_mem,Finset.mem_filter.mp,Finset.min'_le,Fin.extprivate 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
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.
uses
in833_oriented_no_sinks,in833_oriented_low_witness,Finset.mem_filter.mprprivate 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
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.
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.elimprivate 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
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.
uses
Finset.disjoint_left.mp,in833_oriented_cycle_avoids_target_contains_parents,in833_oriented_cycle_successor,in833_oriented_every_successor_set_hits_parentprivate 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
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.
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_twoprivate 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
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.
uses
in833_oriented_cut20_orientation,in833_oriented_cut20_degree,in833_oriented_cut20_boundary,in833_oriented_no_two,in833_oriented_robusttheorem 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.
- The properties of orientation, outdegree 7 on B, and boundary cut size 20 are verified by exhaustive finite computation via the `decide` tactic.
- The helper theorem `in833_oriented_has_parent` (lines 67–106) establishes an earlier, conditional version of hitting the 7-cycle, but the certificate relies on the more general `in833_oriented_every_successor_set_hits_parent`.
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 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⟩