digraph_oriented_regular_cut20_extension_certificate
The extended example is oriented, seven-outregular, arc-dominated and strongly connected, with a twenty-vertex part of cut twenty and no two disjoint cycles; its common-predecessor graph has an independent set of four.
Statement
theorem digraph_oriented_regular_cut20_extension_certificate : let D := digraph_oriented_regular_cut20_extension let B : Finset (Fin 104) := Finset.univ.filter fun v => v.val < 20 let I : Finset (Fin 104) := {0,13,28,35} (∀ u v, D.Adj u v → ¬ D.Adj v u) ∧ (∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7) ∧ (∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) ∧ (∀ u v, Relation.ReflTransGen D.Adj u v) ∧ (∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card) = 20 ∧ (¬ ∃ c : Fin 2 → Finset (Fin 104), (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) ∧ (∀ u ∈ I, ∀ v ∈ I, u ≠ v → ¬ ∃ w, D.Adj w u ∧ D.Adj w v)
- Source
- Finite construction and checks in experiment 26337; the independent set records the limitation for the critical reduction.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- digraph_oriented_regular_cut20_extensionAn explicit strongly connected 104-vertex extension of the oriented 20-cut example using twelve seven-vertex regular tournaments.
- digraph_oriented_cut20_sharp_example_certificateThe explicit oriented example has a seven-outregular twenty-vertex part with twenty outgoing arcs and no two disjoint cycles; every…
- 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…
- 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.
The proof, explained
The 104-vertex digraph is certified to satisfy all seven properties of the certificate. Properties 1, 2, 3, 5, and 7 (orientation, 7-out-regularity, arc-domination, cut size 20, and an independent set of size four in the common-predecessor graph) are closed directly by finite exhaustion via `decide`. Strong connectivity (property 4) is established by proving that every vertex can reach vertex 0 in at most three steps, vertex 0 reaches thirteen 'leader' vertices via an explicit directed path, and every vertex is reached from a leader in at most two steps. Finally, the absence of two disjoint directed cycles within the cut set B (property 6) is proved by transferring any hypothetical disjoint cycles in B to the 26-vertex sharp example via an injective projection, which contradicts the known cycle bound for that graph.
Adjacency in the 104-vertex graph is decidable. automation
Unfolding the definition of the adjacency relation for the 104-vertex graph expresses it as a Boolean combination of decidable equalities and inequalities on finite numbers, allowing typeclass synthesis (`infer_instance`) to infer decidability of adjacency.
private instance in833_regular_extension_decAdj : DecidableRel digraph_oriented_regular_cut20_extension.Adj := by unfold digraph_oriented_regular_cut20_extension infer_instance
The projection to26 from Fin 104 to Fin 26 is defined, and it preserves the numerical value of any vertex with value strictly less than 20.
Opening the `Relation` namespace sets up relational notation. The projection `to26 x` is defined by sending x to itself when its value is below 26 and to 0 otherwise. For vertices with value below 20, linear arithmetic (`omega`) confirms `x.val < 26`, and `dif_pos` selects the positive branch, proving that the projected vertex has the exact same underlying value `x.val`.
uses
dif_posopen Relation def to26 (x : Fin 104) : Fin 26 := if h : x.val < 26 then ⟨x.val, h⟩ else 0 lemma to26_val {x : Fin 104} (h : x.val < 20) : (to26 x).val = x.val := by dsimp [to26] have : x.val < 26 := by omega rw [dif_pos this]
On vertices with value below 20, adjacency in the 104-vertex graph coincides with adjacency in the 26-vertex sharp example.
By `to26_val`, the projection leaves the values of u and v unchanged. The clauses defining adjacency in the 104-vertex graph with u ≥ 20 are false because u < 20 (by linear arithmetic via `omega`), so simplification leaves exactly the four clauses defining adjacency in the 26-vertex sharp example.
uses
to26_valtheorem adj_agree : ∀ (u v : Fin 104), u.val < 20 → v.val < 20 → (digraph_oriented_regular_cut20_extension.Adj u v ↔ digraph_oriented_cut20_sharp_example.Adj (to26 u) (to26 v)) := by intro u v hu hv have h1 := to26_val hu have h2 := to26_val hv dsimp [digraph_oriented_regular_cut20_extension, digraph_oriented_cut20_sharp_example] rw [h1, h2] have hu20 : ¬ (20 ≤ u.val) := by omega simp [hu20]
The projection to26 is injective on the subset of vertices with value strictly less than 20.
Assuming `to26 u = to26 v` for vertices u and v with value below 20, applying `to26_val` gives `u.val = (to26 u).val = (to26 v).val = v.val`. By `Fin.ext`, equality of values implies u = v.
uses
Fin.ext,to26_vallemma to26_injOn_B : Set.InjOn to26 {x : Fin 104 | x.val < 20} := by intro u hu v hv heq apply Fin.ext rw [← to26_val (show u.val < 20 from hu), ← to26_val (show v.val < 20 from hv)] exact congrArg Fin.val heq
Any directed cycle whose vertices lie in B transfers to a directed cycle in the 26-vertex sharp example under to26.
A directed cycle on s ⊆ B is represented by a duplicate-free list l of length at least 2 whose elements form a directed chain with a closing edge from last to head. Since all elements lie in B and `to26` is injective on B by `to26_injOn_B`, the image list `List.map to26 l` has no duplicates (`List.Nodup.map_on`), preserves length (`List.length_map`), and has image set `s.image to26`. Adjacency along the chain and on the closing edge is preserved because all elements have values below 20, so `adj_agree` applies across the chain (`List.isChain_map`, `List.IsChain.imp_of_mem_imp`) and at the endpoints (`List.head?_map`, `List.getLast?_map`, `List.mem_of_mem_head?`, `List.mem_of_mem_getLast?`).
uses
to26_injOn_B,List.Nodup.map_on,List.length_map,Finset.mem_image,List.mem_toFinset,List.mem_map,List.isChain_map,List.IsChain.imp_of_mem_imp,adj_agree,List.head?_map,List.getLast?_map,List.mem_of_mem_head?,List.mem_of_mem_getLast?lemma cycle_transfer (s : Finset (Fin 104)) (hs : ∀ x ∈ s, x.val < 20) (hc : digraph_directed_cycle_on digraph_oriented_regular_cut20_extension s) : digraph_directed_cycle_on digraph_oriented_cut20_sharp_example (s.image to26) := by rcases hc with ⟨l, hnodup, hlen, hto, hchain, a, b, hhead, hlast, hadj⟩ have hmem : ∀ x ∈ l, x ∈ s := fun x hx => by rw [← hto]; exact List.mem_toFinset.mpr hx have hsub' : ∀ x ∈ l, x.val < 20 := fun x hx => hs x (hmem x hx) refine ⟨l.map to26, ?_, ?_, ?_, ?_, to26 a, to26 b, ?_, ?_, ?_⟩ · exact List.Nodup.map_on (fun x hx y hy hxy => to26_injOn_B (hsub' x hx) (hsub' y hy) hxy) hnodup · rwa [List.length_map] · ext y simp only [Finset.mem_image, List.mem_toFinset, List.mem_map] constructor · rintro ⟨x, hx, rfl⟩; exact ⟨x, hmem x hx, rfl⟩ · rintro ⟨x, hx, rfl⟩; rw [← hto] at hx; exact ⟨x, List.mem_toFinset.mp hx, rfl⟩ · rw [List.isChain_map] apply List.IsChain.imp_of_mem_imp _ hchain intro x y hx hy hxy rwa [← adj_agree x y (hsub' x hx) (hsub' y hy)] · rw [List.head?_map, hhead]; rfl · rw [List.getLast?_map, hlast]; rfl · have ha : a.val < 20 := hsub' a (List.mem_of_mem_head? hhead) have hb : b.val < 20 := hsub' b (List.mem_of_mem_getLast? hlast) rwa [← adj_agree b a hb ha]
The thirteen leader vertices are defined, and vertex 0 has a directed path to each of them.
The set of thirteen leader vertices is defined as the start of each regular block plus 0. The existence of directed edges along the spine 0 → 20 → 27 → 34 → 41 → 48 → 55 → 62 → 69 → 76 → 83 → 90 → 97 is verified by `decide`. Using reflexivity and transitivity of `ReflTransGen`, vertex 0 reaches each leader. Rewriting membership in `leaders` with `Finset.mem_insert` and `Finset.mem_singleton`, case analysis establishes the claim for all leaders.
uses
Finset.mem_insert,Finset.mem_singletondef leaders : Finset (Fin 104) := {0, 20, 27, 34, 41, 48, 55, 62, 69, 76, 83, 90, 97} lemma reflTransGen_leaders (v : Fin 104) (hv : v ∈ leaders) : ReflTransGen digraph_oriented_regular_cut20_extension.Adj 0 v := by have a0_20 : digraph_oriented_regular_cut20_extension.Adj 0 20 := by decide have a20_27 : digraph_oriented_regular_cut20_extension.Adj 20 27 := by decide have a27_34 : digraph_oriented_regular_cut20_extension.Adj 27 34 := by decide have a34_41 : digraph_oriented_regular_cut20_extension.Adj 34 41 := by decide have a41_48 : digraph_oriented_regular_cut20_extension.Adj 41 48 := by decide have a48_55 : digraph_oriented_regular_cut20_extension.Adj 48 55 := by decide have a55_62 : digraph_oriented_regular_cut20_extension.Adj 55 62 := by decide have a62_69 : digraph_oriented_regular_cut20_extension.Adj 62 69 := by decide have a69_76 : digraph_oriented_regular_cut20_extension.Adj 69 76 := by decide have a76_83 : digraph_oriented_regular_cut20_extension.Adj 76 83 := by decide have a83_90 : digraph_oriented_regular_cut20_extension.Adj 83 90 := by decide have a90_97 : digraph_oriented_regular_cut20_extension.Adj 90 97 := by decide have p0 : ReflTransGen digraph_oriented_regular_cut20_extension.Adj 0 0 := ReflTransGen.refl have p20 : ReflTransGen digraph_oriented_regular_cut20_extension.Adj 0 20 := ReflTransGen.single a0_20 have p27 := p20.trans (ReflTransGen.single a20_27) have p34 := p27.trans (ReflTransGen.single a27_34) have p41 := p34.trans (ReflTransGen.single a34_41) have p48 := p41.trans (ReflTransGen.single a41_48) have p55 := p48.trans (ReflTransGen.single a48_55) have p62 := p55.trans (ReflTransGen.single a55_62) have p69 := p62.trans (ReflTransGen.single a62_69) have p76 := p69.trans (ReflTransGen.single a69_76) have p83 := p76.trans (ReflTransGen.single a76_83) have p90 := p83.trans (ReflTransGen.single a83_90) have p97 := p90.trans (ReflTransGen.single a90_97) simp only [leaders, Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> assumption
The 104-vertex graph is strongly connected.
Exhaustive search by `decide` shows that every vertex u reaches 0 in at most 3 steps, and every vertex v is reachable from some leader in at most 2 steps. Since 0 reaches every leader by `reflTransGen_leaders`, 0 reaches v. Composing the path from u to 0 with the path from 0 to v by transitivity of `ReflTransGen` yields a path from u to v.
uses
reflTransGen_leaderslemma reflTransGen_all (u v : Fin 104) : ReflTransGen digraph_oriented_regular_cut20_extension.Adj u v := by have hto : ∀ u : Fin 104, u = 0 ∨ digraph_oriented_regular_cut20_extension.Adj u 0 ∨ (∃ w : Fin 104, digraph_oriented_regular_cut20_extension.Adj u w ∧ digraph_oriented_regular_cut20_extension.Adj w 0) ∨ (∃ w₁ : Fin 104, ∃ w₂ : Fin 104, digraph_oriented_regular_cut20_extension.Adj u w₁ ∧ digraph_oriented_regular_cut20_extension.Adj w₁ w₂ ∧ digraph_oriented_regular_cut20_extension.Adj w₂ 0) := by decide have hfrom : ∀ v : Fin 104, (v ∈ leaders) ∨ (∃ s ∈ leaders, digraph_oriented_regular_cut20_extension.Adj s v) ∨ (∃ s ∈ leaders, ∃ w : Fin 104, digraph_oriented_regular_cut20_extension.Adj s w ∧ digraph_oriented_regular_cut20_extension.Adj w v) := by decide have u_to_0 : ReflTransGen digraph_oriented_regular_cut20_extension.Adj u 0 := by rcases hto u with rfl | h1 | ⟨w, h1, h2⟩ | ⟨w₁, w₂, h1, h2, h3⟩ · exact ReflTransGen.refl · exact ReflTransGen.single h1 · exact (ReflTransGen.single h1).tail h2 · exact ((ReflTransGen.single h1).tail h2).tail h3 have zero_to_v : ReflTransGen digraph_oriented_regular_cut20_extension.Adj 0 v := by rcases hfrom v with hv | ⟨s, hs, h1⟩ | ⟨s, hs, w, h1, h2⟩ · exact reflTransGen_leaders v hv · exact (reflTransGen_leaders s hs).tail h1 · exact ((reflTransGen_leaders s hs).tail h1).tail h2 exact u_to_0.trans zero_to_v
The extended graph is oriented, 7-out-regular, arc-dominated, strongly connected, and has cut size 20 across B.
Properties 1 (orientation), 2 (every vertex has out-degree 7), 3 (every arc has a common in-neighbour), and 5 (the number of edges directed from B to Bᶜ equals 20) are verified by `decide`. Property 4 (strong connectivity) is supplied directly by `reflTransGen_all`.
uses
reflTransGen_alltheorem digraph_oriented_regular_cut20_extension_certificate : let D := digraph_oriented_regular_cut20_extension let B : Finset (Fin 104) := Finset.univ.filter fun v => v.val < 20 let I : Finset (Fin 104) := {0,13,28,35} (∀ u v, D.Adj u v → ¬ D.Adj v u) ∧ (∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7) ∧ (∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) ∧ (∀ u v, Relation.ReflTransGen D.Adj u v) ∧ (∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card) = 20 ∧ (¬ ∃ c : Fin 2 → Finset (Fin 104), (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) ∧ (∀ u ∈ I, ∀ v ∈ I, u ≠ v → ¬ ∃ w, D.Adj w u ∧ D.Adj w v) := by dsimp only refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ · decide · decide · decide · exact reflTransGen_all · decide
There do not exist two vertex-disjoint directed cycles contained in B.
Suppose for contradiction two disjoint cycles c 0 and c 1 exist within B. By `cycle_transfer`, their images under `to26` are directed cycles in the 26-vertex sharp example. Because `to26` is injective on B (`to26_injOn_B`), the disjointness of c 0 and c 1 implies their images are also disjoint. This contradicts the certificate for the 26-vertex sharp example, which states that no two disjoint directed cycles exist.
uses
cycle_transfer,to26_injOn_B· rintro ⟨c, hcyc, hdisj⟩ refine digraph_oriented_cut20_sharp_example_certificate.2.2.2.1 ⟨fun i => (c i).image to26, ?_, ?_⟩ · intro i exact cycle_transfer (c i) (fun x hx => by have := (hcyc i).1 hx; simpa using this) (hcyc i).2 · intro i j hij refine Finset.disjoint_left.2 fun x hx1 hx2 => ?_ obtain ⟨a, ha, rfl⟩ := Finset.mem_image.1 hx1 obtain ⟨b, hb, hba⟩ := Finset.mem_image.1 hx2 have hia : a.val < 20 := by have := (hcyc i).1 ha; simpa using this have hjb : b.val < 20 := by have := (hcyc j).1 hb; simpa using this have hab : a = b := to26_injOn_B hia hjb hba.symm have hdis : Disjoint (c i) (c j) := hdisj hij rw [← hab] at hb exact (Finset.disjoint_left.1 hdis ha) hbThe set I = {0, 13, 28, 35} is an independent set in the common-predecessor graph. automation
The condition that no two distinct vertices in I share an in-neighbour in the 104-vertex graph is a finite check closed by `decide`.
· decide
adj_agree- For vertices u, v in Fin 104 with values strictly less than 20, adjacency in the 104-vertex graph is equivalent to adjacency between their projections to26(u) and to26(v) in the 26-vertex sharp example.
cycle_transfer- Any directed cycle in the 104-vertex graph whose vertices all have values less than 20 maps via to26 to a directed cycle in the 26-vertex sharp example.
dif_pos- When condition c is true, the dependent if-then-else `if h : c then t else e` reduces to `t hc`.
Fin.ext- Two elements of Fin n are equal if their underlying natural number values are equal.
Finset.mem_image- An element b belongs to the image of a finite set s under f if and only if there exists a in s such that f(a) = b.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
List.head?_map- The optional head of List.map f l is the image under f of the optional head of l.
List.IsChain.imp_of_mem_imp- A list is a chain under relation S if it is a chain under R and R implies S for all pairs of elements from the list.
List.isChain_map- The mapped list List.map f l is a chain under relation R if and only if l is a chain under the relation pulled back by f.
List.getLast?_map- The optional last element of List.map f l is the image under f of the optional last element of l.
List.length_map- Mapping a function over a list preserves the length of the list.
List.mem_map- An element belongs to a mapped list if and only if it is the image of an element in the original list.
List.mem_of_mem_head?- If an element is the head of a list, then it is an element of that list.
List.mem_of_mem_getLast?- If an element is the last element of a list, then it is an element of that list.
List.mem_toFinset- An element belongs to the finite set formed from a list if and only if it belongs to the list.
List.Nodup.map_on- Mapping a duplicate-free list under a function that is injective on the list's elements yields a duplicate-free list.
reflTransGen_all- Between any two vertices in Fin 104, there exists a directed path in the extended graph.
reflTransGen_leaders- Vertex 0 has a directed path in the extended graph to every vertex in the leader set.
to26_injOn_B- The projection to26 is injective on the subset of vertices whose values are strictly less than 20.
to26_val- For any vertex x in Fin 104 with value less than 20, the projection to26(x) has the exact same numerical value as x.
- Properties 1, 2, 3, 5, and 7 of the certificate (orientation, 7-out-regularity, arc-domination, cut size 20, and the independent set in the common-predecessor graph), as well as the short-path reachability bounds used to prove strong connectivity, are proved by exhaustive evaluation over the finite type Fin 104 via the `decide` decision procedure.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
private instance in833_regular_extension_decAdj : DecidableRel digraph_oriented_regular_cut20_extension.Adj := by unfold digraph_oriented_regular_cut20_extension infer_instanceopen Relationdef to26 (x : Fin 104) : Fin 26 := if h : x.val < 26 then ⟨x.val, h⟩ else 0lemma to26_val {x : Fin 104} (h : x.val < 20) : (to26 x).val = x.val := by dsimp [to26] have : x.val < 26 := by omega rw [dif_pos this]theorem adj_agree : ∀ (u v : Fin 104), u.val < 20 → v.val < 20 → (digraph_oriented_regular_cut20_extension.Adj u v ↔ digraph_oriented_cut20_sharp_example.Adj (to26 u) (to26 v)) := by intro u v hu hv have h1 := to26_val hu have h2 := to26_val hv dsimp [digraph_oriented_regular_cut20_extension, digraph_oriented_cut20_sharp_example] rw [h1, h2] have hu20 : ¬ (20 ≤ u.val) := by omega simp [hu20]lemma to26_injOn_B : Set.InjOn to26 {x : Fin 104 | x.val < 20} := by intro u hu v hv heq apply Fin.ext rw [← to26_val (show u.val < 20 from hu), ← to26_val (show v.val < 20 from hv)] exact congrArg Fin.val heqlemma cycle_transfer (s : Finset (Fin 104)) (hs : ∀ x ∈ s, x.val < 20) (hc : digraph_directed_cycle_on digraph_oriented_regular_cut20_extension s) : digraph_directed_cycle_on digraph_oriented_cut20_sharp_example (s.image to26) := by rcases hc with ⟨l, hnodup, hlen, hto, hchain, a, b, hhead, hlast, hadj⟩ have hmem : ∀ x ∈ l, x ∈ s := fun x hx => by rw [← hto]; exact List.mem_toFinset.mpr hx have hsub' : ∀ x ∈ l, x.val < 20 := fun x hx => hs x (hmem x hx) refine ⟨l.map to26, ?_, ?_, ?_, ?_, to26 a, to26 b, ?_, ?_, ?_⟩ · exact List.Nodup.map_on (fun x hx y hy hxy => to26_injOn_B (hsub' x hx) (hsub' y hy) hxy) hnodup · rwa [List.length_map] · ext y simp only [Finset.mem_image, List.mem_toFinset, List.mem_map] constructor · rintro ⟨x, hx, rfl⟩; exact ⟨x, hmem x hx, rfl⟩ · rintro ⟨x, hx, rfl⟩; rw [← hto] at hx; exact ⟨x, List.mem_toFinset.mp hx, rfl⟩ · rw [List.isChain_map] apply List.IsChain.imp_of_mem_imp _ hchain intro x y hx hy hxy rwa [← adj_agree x y (hsub' x hx) (hsub' y hy)] · rw [List.head?_map, hhead]; rfl · rw [List.getLast?_map, hlast]; rfl · have ha : a.val < 20 := hsub' a (List.mem_of_mem_head? hhead) have hb : b.val < 20 := hsub' b (List.mem_of_mem_getLast? hlast) rwa [← adj_agree b a hb ha]def leaders : Finset (Fin 104) := {0, 20, 27, 34, 41, 48, 55, 62, 69, 76, 83, 90, 97}lemma reflTransGen_leaders (v : Fin 104) (hv : v ∈ leaders) : ReflTransGen digraph_oriented_regular_cut20_extension.Adj 0 v := by have a0_20 : digraph_oriented_regular_cut20_extension.Adj 0 20 := by decide have a20_27 : digraph_oriented_regular_cut20_extension.Adj 20 27 := by decide have a27_34 : digraph_oriented_regular_cut20_extension.Adj 27 34 := by decide have a34_41 : digraph_oriented_regular_cut20_extension.Adj 34 41 := by decide have a41_48 : digraph_oriented_regular_cut20_extension.Adj 41 48 := by decide have a48_55 : digraph_oriented_regular_cut20_extension.Adj 48 55 := by decide have a55_62 : digraph_oriented_regular_cut20_extension.Adj 55 62 := by decide have a62_69 : digraph_oriented_regular_cut20_extension.Adj 62 69 := by decide have a69_76 : digraph_oriented_regular_cut20_extension.Adj 69 76 := by decide have a76_83 : digraph_oriented_regular_cut20_extension.Adj 76 83 := by decide have a83_90 : digraph_oriented_regular_cut20_extension.Adj 83 90 := by decide have a90_97 : digraph_oriented_regular_cut20_extension.Adj 90 97 := by decide have p0 : ReflTransGen digraph_oriented_regular_cut20_extension.Adj 0 0 := ReflTransGen.refl have p20 : ReflTransGen digraph_oriented_regular_cut20_extension.Adj 0 20 := ReflTransGen.single a0_20 have p27 := p20.trans (ReflTransGen.single a20_27) have p34 := p27.trans (ReflTransGen.single a27_34) have p41 := p34.trans (ReflTransGen.single a34_41) have p48 := p41.trans (ReflTransGen.single a41_48) have p55 := p48.trans (ReflTransGen.single a48_55) have p62 := p55.trans (ReflTransGen.single a55_62) have p69 := p62.trans (ReflTransGen.single a62_69) have p76 := p69.trans (ReflTransGen.single a69_76) have p83 := p76.trans (ReflTransGen.single a76_83) have p90 := p83.trans (ReflTransGen.single a83_90) have p97 := p90.trans (ReflTransGen.single a90_97) simp only [leaders, Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> assumptionlemma reflTransGen_all (u v : Fin 104) : ReflTransGen digraph_oriented_regular_cut20_extension.Adj u v := by have hto : ∀ u : Fin 104, u = 0 ∨ digraph_oriented_regular_cut20_extension.Adj u 0 ∨ (∃ w : Fin 104, digraph_oriented_regular_cut20_extension.Adj u w ∧ digraph_oriented_regular_cut20_extension.Adj w 0) ∨ (∃ w₁ : Fin 104, ∃ w₂ : Fin 104, digraph_oriented_regular_cut20_extension.Adj u w₁ ∧ digraph_oriented_regular_cut20_extension.Adj w₁ w₂ ∧ digraph_oriented_regular_cut20_extension.Adj w₂ 0) := by decide have hfrom : ∀ v : Fin 104, (v ∈ leaders) ∨ (∃ s ∈ leaders, digraph_oriented_regular_cut20_extension.Adj s v) ∨ (∃ s ∈ leaders, ∃ w : Fin 104, digraph_oriented_regular_cut20_extension.Adj s w ∧ digraph_oriented_regular_cut20_extension.Adj w v) := by decide have u_to_0 : ReflTransGen digraph_oriented_regular_cut20_extension.Adj u 0 := by rcases hto u with rfl | h1 | ⟨w, h1, h2⟩ | ⟨w₁, w₂, h1, h2, h3⟩ · exact ReflTransGen.refl · exact ReflTransGen.single h1 · exact (ReflTransGen.single h1).tail h2 · exact ((ReflTransGen.single h1).tail h2).tail h3 have zero_to_v : ReflTransGen digraph_oriented_regular_cut20_extension.Adj 0 v := by rcases hfrom v with hv | ⟨s, hs, h1⟩ | ⟨s, hs, w, h1, h2⟩ · exact reflTransGen_leaders v hv · exact (reflTransGen_leaders s hs).tail h1 · exact ((reflTransGen_leaders s hs).tail h1).tail h2 exact u_to_0.trans zero_to_vtheorem digraph_oriented_regular_cut20_extension_certificate : let D := digraph_oriented_regular_cut20_extension let B : Finset (Fin 104) := Finset.univ.filter fun v => v.val < 20 let I : Finset (Fin 104) := {0,13,28,35} (∀ u v, D.Adj u v → ¬ D.Adj v u) ∧ (∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7) ∧ (∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) ∧ (∀ u v, Relation.ReflTransGen D.Adj u v) ∧ (∑ v ∈ B, (Bᶜ.filter fun w => D.Adj v w).card) = 20 ∧ (¬ ∃ c : Fin 2 → Finset (Fin 104), (∀ i, c i ⊆ B ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) ∧ (∀ u ∈ I, ∀ v ∈ I, u ≠ v → ¬ ∃ w, D.Adj w u ∧ D.Adj w v) := by dsimp only refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ · decide · decide · decide · exact reflTransGen_all · decide · rintro ⟨c, hcyc, hdisj⟩ refine digraph_oriented_cut20_sharp_example_certificate.2.2.2.1 ⟨fun i => (c i).image to26, ?_, ?_⟩ · intro i exact cycle_transfer (c i) (fun x hx => by have := (hcyc i).1 hx; simpa using this) (hcyc i).2 · intro i j hij refine Finset.disjoint_left.2 fun x hx1 hx2 => ?_ obtain ⟨a, ha, rfl⟩ := Finset.mem_image.1 hx1 obtain ⟨b, hb, hba⟩ := Finset.mem_image.1 hx2 have hia : a.val < 20 := by have := (hcyc i).1 ha; simpa using this have hjb : b.val < 20 := by have := (hcyc j).1 hb; simpa using this have hab : a = b := to26_injOn_B hia hjb hba.symm have hdis : Disjoint (c i) (c j) := hdisj hij rw [← hab] at hb exact (Finset.disjoint_left.1 hdis ha) hb · decide