AFTD Auto-Formalizing Theoretical Domains

digraph_oriented_regular_cut20_extension_certificate

theoremverified

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

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.

  1. 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.

    lines 1–3

    private instance in833_regular_extension_decAdj : DecidableRel digraph_oriented_regular_cut20_extension.Adj := by
      unfold digraph_oriented_regular_cut20_extension
      infer_instance
  2. 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`.

    lines 5–14

    uses dif_pos

    open 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]
    
  3. 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.

    lines 15–26

    uses to26_val

    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]
    
  4. 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.

    lines 27–32

    uses Fin.ext, to26_val

    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 heq
    
  5. 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?`).

    lines 33–57

    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]
    
  6. 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.

    lines 58–89

    uses Finset.mem_insert, Finset.mem_singleton

    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 <;> assumption
    
  7. 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.

    lines 90–109

    uses reflTransGen_leaders

    lemma 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
    
  8. 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`.

    lines 110–128

    uses reflTransGen_all

    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) := by
      dsimp only
      refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
      · decide
      · decide
      · decide
      · exact reflTransGen_all
      · decide
  9. 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.

    lines 129–144

    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) hb
  10. The 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`.

    line 145

      · 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.

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
See it in the graphDiscuss this resultChallenge it