AFTD Auto-Formalizing Theoretical Domains

digraph_16_shared_target_forces_two_cycles

theoremverified

The normalized oriented sixteen-vertex shared-target configuration contains two disjoint cycles, assuming the displayed two-cycle criterion.

Statement

theorem digraph_16_shared_target_forces_two_cycles
    (D : Digraph (Fin 16)) [DecidableRel D.Adj]
    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)
    (hdeg : ∀ v : Fin 16, 5 ≤ v.val →
      (Finset.univ.filter fun w => D.Adj v w).card = 7)
    (hlow : ∀ v : Fin 16, v.val < 5 → D.Adj v 8)
    (hout : ∀ v : Fin 16, 9 ≤ v.val → D.Adj 8 v)
    (htwo : ∀ T : Finset (Fin 16), T.Nonempty →
      (∀ v ∈ T, 3 ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ c : Fin 2 → Finset (Fin 16), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j))) :
    ∃ c : Fin 2 → Finset (Fin 16),
      (∀ i, digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j))
Source
Common-cycle core route for the first remaining oriented twenty-cut equality-profile size in OP-110.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8

The proof, explained

The proof proceeds by contradiction, assuming that the 16-vertex oriented digraph contains no two disjoint directed cycles. Under this assumption, a known lemma forces the set S of high-index vertices (r ≥ 9) sending an arc to low-index vertices (< 5) to have |S| ≥ 4. Any cycle in H = {v ≥ 5 | v ≠ 8} must contain S, for otherwise a missing vertex in S closes a disjoint directed triangle through 8 and a low vertex. In a sink strongly connected component T ⊆ H, every cycle contains S, which forces |T \ S| ≥ |S| ≥ 4; however, high out-degrees force T to be disjoint from R \ S, giving T \ S ⊆ P = {5, 6, 7} and hence |T \ S| ≤ 3, a contradiction.

  1. Assume for contradiction that no two disjoint cycles exist, and deduce that |S| ≥ 4.

    We assume for contradiction that D contains no two vertex-disjoint directed cycles (hno). Because D is oriented, it contains no self-loops (hloop). We partition the vertices into subsets according to their values: R = {v | 9 ≤ v}, P = {v | 5 ≤ v < 8}, H = {v | 5 ≤ v ∧ v ≠ 8}, and S = {r ∈ R | ∃ v < 5, D.Adj r v}. By digraph_16_shared_target_many_low_arcs, the absence of two disjoint cycles forces S to contain at least 4 vertices (|S| ≥ 4).

    lines 15–23

    uses digraph_16_shared_target_many_low_arcs

      classical
      by_contra hno
      have hloop : ∀ v, ¬ D.Adj v v := fun v hv => hori v v hv hv
      let R : Finset (Fin 16) := Finset.univ.filter fun v => 9 ≤ v.val
      let P : Finset (Fin 16) := Finset.univ.filter fun v => 5 ≤ v.val ∧ v.val < 8
      let H : Finset (Fin 16) := Finset.univ.filter fun v => 5 ≤ v.val ∧ v.val ≠ 8
      let S : Finset (Fin 16) := Finset.univ.filter fun r => 9 ≤ r.val ∧ ∃ v : Fin 16, v.val < 5 ∧ D.Adj r v
      have hScard : 4 ≤ S.card :=
        digraph_16_shared_target_many_low_arcs D hori (fun v hv => hdeg v (by omega)) hlow hout htwo hno
  2. H contains a nonempty sink strongly connected induced subgraph T.

    Since 5 ∈ H, H is nonempty. By digraph_finite_sink_strong_subgraph, any nonempty finite induced subgraph contains a sink strongly connected component T ⊆ H: T is nonempty, strongly connected, and all out-arcs from T into H remain within T.

    lines 24–25

    uses digraph_finite_sink_strong_subgraph

      have hHne : H.Nonempty := ⟨(5 : Fin 16), by decide⟩
      obtain ⟨T, hTH, hTne, hsink, hstrong⟩ := digraph_finite_sink_strong_subgraph (Fin 16) D H hHne
  3. Any directed cycle in H must contain all vertices of S.

    Suppose for contradiction that some directed cycle C ⊆ H misses a vertex s ∈ S. By definition of S, there exists a low vertex v < 5 such that s → v. From the hypotheses, v → 8 and 8 → s, forming a directed triangle on {v, 8, s}. Since v < 5 and 8 ∉ H, neither v nor 8 is in H; and since s ∉ C, the triangle {v, 8, s} is vertex-disjoint from C. This yields two disjoint directed cycles in D, contradicting the assumption hno. Hence S ⊆ C.

    lines 26–58

    uses Finset.mem_filter, List.isChain_cons_cons, Finset.disjoint_left

      have hcore_H (C : Finset (Fin 16)) (hCH : C ⊆ H) (hC : digraph_directed_cycle_on D C) : S ⊆ C := by
        intro s hs
        rw [Finset.mem_filter] at hs
        obtain ⟨-, hsval, v, hvval, hsv⟩ := hs
        by_contra hsC
        have hv8 : v ≠ (8 : Fin 16) := by intro h; have := congrArg Fin.val h; norm_num at this; omega
        have hvs : v ≠ s := by intro h; have := congrArg Fin.val h; omega
        have h8s : (8 : Fin 16) ≠ s := by intro h; have := congrArg Fin.val h; norm_num at this; omega
        have htri : digraph_directed_cycle_on D ({v,8,s} : Finset (Fin 16)) := by
          refine ⟨[v,8,s], ?_, by simp, by simp, ?_, ?_⟩
          · simp [hv8,hvs,h8s]
          · simpa [List.isChain_cons_cons] using ⟨hlow v hvval, hout s hsval⟩
          · exact ⟨v,s,by simp,by simp,hsv⟩
        have hdis : Disjoint ({v,8,s} : Finset (Fin 16)) C := by
          rw [Finset.disjoint_left]
          intro x hx hxC
          have hxH : x ∈ H := hCH hxC
          rw [Finset.mem_filter] at hxH
          simp only [Finset.mem_insert, Finset.mem_singleton] at hx
          rcases hx with rfl | rfl | rfl
          · omega
          · exact hxH.2.2 rfl
          · exact hsC hxC
        let f : Fin 2 → Finset (Fin 16) := Fin.cases {v,8,s} (fun _ => C)
        apply hno
        refine ⟨f, ?_, ?_⟩
        · intro i
          fin_cases i
          · exact htri
          · exact hC
        · intro i j hij
          fin_cases i <;> fin_cases j <;>
            first | exact (hij rfl).elim | exact hdis | exact hdis.symm
  4. T contains a directed cycle, which forces S ⊆ T, and every directed cycle in T contains S.

    Every vertex v ∈ T ⊆ H has out-degree 7 in D. Since the complement Hᶜ = {0, 1, 2, 3, 4, 8} has cardinality 6, v must have at least one out-neighbor in H by Finset.card_le_card and Finset.not_subset. Because T is a sink in H, this out-neighbor lies in T. Since every vertex in T has an out-neighbor in T, by digraph_low_cut_contains_cycle_outdeg_cycle T contains a directed cycle C. Because C ⊆ T ⊆ H, the previous step gives S ⊆ C ⊆ T. It follows that every directed cycle in T contains S.

    lines 59–79

    uses Finset.card_le_card, Finset.not_subset, digraph_low_cut_contains_cycle_outdeg_cycle

      have hsucc : ∀ v ∈ T, ∃ w ∈ T, D.Adj v w := by
        intro v hv
        have hvH : v ∈ H := hTH hv
        rw [Finset.mem_filter] at hvH
        let N := Finset.univ.filter fun w => D.Adj v w
        have h7 : N.card = 7 := hdeg v hvH.2.1
        have hHc : (Hᶜ : Finset (Fin 16)).card = 6 := by decide
        have hNne : ¬ (N ⊆ Hᶜ) := by
          intro hsub
          have := Finset.card_le_card hsub
          omega
        rw [Finset.not_subset] at hNne
        obtain ⟨w, hwN, hwHc⟩ := hNne
        rw [Finset.mem_compl] at hwHc
        have hwH : w ∈ H := Classical.not_not.mp hwHc
        rw [Finset.mem_filter] at hwN
        exact ⟨w, hsink v hv w hwH hwN.2, hwN.2⟩
      obtain ⟨C, hCT, hC⟩ := digraph_low_cut_contains_cycle_outdeg_cycle (Fin 16) D hloop T hTne hsucc
      have hST : S ⊆ T := (hcore_H C (hCT.trans hTH) hC).trans hCT
      have hcore_T : ∀ C ⊆ T, digraph_directed_cycle_on D C → S ⊆ C :=
        fun C hCsub hCcyc => hcore_H C (hCsub.trans hTH) hCcyc
  5. Every vertex in S has out-degree at least 2 in T, which forces |T \ S| ≥ 4.

    For each s ∈ S, s ≥ 9, so s cannot send an arc to 8 because 8 → s and D is oriented. Thus all out-neighbors of s in Hᶜ must belong to {0, 1, 2, 3, 4}, which has cardinality 5. Since s has 7 out-neighbors in total, at least 7 - 5 = 2 of them lie in H, and therefore in T because T is a sink in H. By digraph_common_cycle_core_outside_injection, in a strongly connected subgraph where every cycle contains S and every vertex in S has out-degree at least 2, there is an injection from S into T \ S, so |S| ≤ |T \ S|. Combining this with |S| ≥ 4 via le_trans gives |T \ S| ≥ 4, which also shows S is nonempty.

    lines 80–132

    uses Fin.ext, Finset.card_union_of_disjoint, subset_refl, digraph_common_cycle_core_outside_injection, le_trans

      have hs_deg : ∀ s ∈ S, 2 ≤ (T.filter fun w => D.Adj s w).card := by
        intro s hs
        have hsT : s ∈ T := hST hs
        have hsval : 9 ≤ s.val := (Finset.mem_filter.mp hs).2.1
        have hn8 : ¬ D.Adj s 8 := hori 8 s (hout s hsval)
        let N := Finset.univ.filter fun w => D.Adj s w
        have hNcard : N.card = 7 := hdeg s (by omega)
        let L : Finset (Fin 16) := Finset.univ.filter fun w => w.val < 5
        have hLcard : L.card = 5 := by decide
        let Nc := Hᶜ.filter fun w => D.Adj s w
        have hNcsub : Nc ⊆ L := by
          intro w hw
          have hadj : D.Adj s w := (Finset.mem_filter.mp hw).2
          have hnotH : w ∉ H := (Finset.mem_compl.mp (Finset.mem_filter.mp hw).1)
          have hwlow : w.val < 5 := by
            by_contra hcon
            have h5 : 5 ≤ w.val := by omega
            have hne8 : w.val ≠ 8 := by
              intro heq
              have : w = 8 := Fin.ext heq
              subst w
              exact hn8 hadj
            apply hnotH
            exact Finset.mem_filter.mpr ⟨Finset.mem_univ w, h5, hne8⟩
          exact Finset.mem_filter.mpr ⟨Finset.mem_univ w, hwlow⟩
        have hNccard : Nc.card ≤ 5 := by
          have := Finset.card_le_card hNcsub
          omega
        let Nh := H.filter fun w => D.Adj s w
        have hNh_eq : Nh = T.filter fun w => D.Adj s w := by
          ext w
          simp only [Finset.mem_filter, Nh]
          constructor
          · rintro ⟨hwH, hadj⟩
            exact ⟨hsink s hsT w hwH hadj, hadj⟩
          · rintro ⟨hwT, hadj⟩
            exact ⟨hTH hwT, hadj⟩
        have hdecomp : N = Nh ∪ Nc := by
          ext w
          simp only [N, Nh, Nc, Finset.mem_filter, Finset.mem_union, Finset.mem_compl, Finset.mem_univ, true_and]
          by_cases hw : w ∈ H <;> simp [hw]
        have hdisj : Disjoint Nh Nc := by
          rw [Finset.disjoint_left]
          intro x hx1 hx2
          have : x ∉ H := Finset.mem_compl.mp (Finset.mem_filter.mp hx2).1
          exact this (Finset.mem_filter.mp hx1).1
        have hsum : N.card = Nh.card + Nc.card := by
          rw [hdecomp, Finset.card_union_of_disjoint hdisj]
        rw [hNh_eq] at hsum
        omega
      have hinj := digraph_common_cycle_core_outside_injection (Fin 16) D T S S hST (subset_refl S) hloop hstrong hcore_T hs_deg
      have hdiff4 : 4 ≤ (T \ S).card := le_trans hScard hinj
      have hneS : S.Nonempty := Finset.card_pos.mp (by omega)
  6. T ⊆ R ∪ P, |P| + 2 ≤ 5, and every vertex in T has at most one out-neighbor in S.

    Any vertex in H satisfies v ≥ 5 and v ≠ 8, so either 5 ≤ v < 8 (so v ∈ P) or v ≥ 9 (so v ∈ R); thus T ⊆ H ⊆ R ∪ P. The set P = {5, 6, 7} has 3 elements, so |P| + 2 ≤ 5. Furthermore, by digraph_common_cycle_core_neighbor_unique, any vertex in a strongly connected subgraph where every cycle contains S can have at most one out-neighbor in S.

    lines 133–148

    uses digraph_common_cycle_core_neighbor_unique

      have hcover : T ⊆ R ∪ P := by
        intro x hx
        have hxH := hTH hx
        rw [Finset.mem_filter] at hxH
        rw [Finset.mem_union, Finset.mem_filter, Finset.mem_filter]
        by_cases hx8 : x.val < 8
        · right
          exact ⟨Finset.mem_univ x, hxH.2.1, hx8⟩
        · left
          have : 9 ≤ x.val := by
            have : x.val ≠ 8 := hxH.2.2
            omega
          exact ⟨Finset.mem_univ x, this⟩
      have hPcard : P.card + 2 ≤ 5 := by decide
      have huniq (x : Fin 16) (hx : x ∈ T) : (S.filter fun y => D.Adj x y).card ≤ 1 :=
        (digraph_common_cycle_core_neighbor_unique (Fin 16) D T S hST hloop hstrong hcore_T x hx).1
  7. Vertices in T ∩ (R \ S) have out-degree at least 5 in T, and T is disjoint from R \ S.

    For any x ∈ T with x ∈ R and x ∉ S, x ≥ 9 implies x has no arc to 8, and x ∉ S implies x has no arcs to vertices below 5. Hence none of the 7 out-neighbors of x lie in Hᶜ, so all 7 lie in H, and thus in T. This gives an out-degree in T of 7 ≥ 5. By digraph_common_cycle_core_excludes_high_degree_vertices with k = 5, since T ⊆ R ∪ P, |P| + 2 ≤ 5, every cycle in T contains S, every vertex in T has at most one out-neighbor in S, and vertices in T ∩ (R \ S) have out-degree at least 5 in T, T must be disjoint from R \ S.

    lines 149–179

    uses Fin.ext, digraph_common_cycle_core_excludes_high_degree_vertices

      have hdeg5 (x : Fin 16) (hxT : x ∈ T) (hxR : x ∈ R) (hxS : x ∉ S) : 5 ≤ (T.filter fun y => D.Adj x y).card := by
        have hxval : 9 ≤ x.val := (Finset.mem_filter.mp hxR).2
        have hn8 : ¬ D.Adj x 8 := hori 8 x (hout x hxval)
        have hnolow : ∀ v : Fin 16, v.val < 5 → ¬ D.Adj x v := by
          intro v hv hadj
          apply hxS
          rw [Finset.mem_filter]
          exact ⟨Finset.mem_univ x, hxval, v, hv, hadj⟩
        let N := Finset.univ.filter fun w => D.Adj x w
        have hNcard : N.card = 7 := hdeg x (by omega)
        have hsubH : N ⊆ H := by
          intro w hw
          rw [Finset.mem_filter] at hw
          rw [Finset.mem_filter]
          refine ⟨Finset.mem_univ w, ?_, ?_⟩
          · by_contra hlt
            have : w.val < 5 := by omega
            exact hnolow w this hw.2
          · intro heq
            have : w = 8 := Fin.ext heq
            subst w
            exact hn8 hw.2
        have hsubT : N ⊆ T.filter fun y => D.Adj x y := by
          intro w hw
          rw [Finset.mem_filter] at hw
          have hwH := hsubH (Finset.mem_filter.mpr hw)
          exact Finset.mem_filter.mpr ⟨hsink x hxT w hwH hw.2, hw.2⟩
        have := Finset.card_le_card hsubT
        omega
      have hdisj_T_RS : Disjoint T (R \ S) :=
        digraph_common_cycle_core_excludes_high_degree_vertices (Fin 16) D T R S P 5 hloop hneS hcover hPcard hcore_T huniq hdeg5
  8. T \ S ⊆ P, which bounds |T \ S| ≤ 3, contradicting |T \ S| ≥ 4.

    Any x ∈ T \ S belongs to R ∪ P. Since T is disjoint from R \ S, x cannot be in R, so x ∈ P. Thus T \ S ⊆ P. Since |P| = 3, Finset.card_le_card gives |T \ S| ≤ 3. Linear arithmetic (omega) detects the contradiction with |T \ S| ≥ 4, finishing the proof.

    lines 180–196

    uses Finset.mem_sdiff, Finset.card_le_card

      have hsubP : T \ S ⊆ P := by
        intro x hx
        rw [Finset.mem_sdiff] at hx
        have hxT := hx.1
        have hxS := hx.2
        have hxRP := hcover hxT
        rw [Finset.mem_union] at hxRP
        rcases hxRP with hxR | hxP
        · exfalso
          have hxRS : x ∈ R \ S := Finset.mem_sdiff.mpr ⟨hxR, hxS⟩
          exact Finset.disjoint_left.mp hdisj_T_RS hxT hxRS
        · exact hxP
      have hP3 : P.card = 3 := by decide
      have hle3 : (T \ S).card ≤ 3 := by
        have := Finset.card_le_card hsubP
        omega
      omega
digraph_16_shared_target_many_low_arcs
In an oriented digraph on 16 vertices satisfying the degree condition for high vertices, the hub condition, and the two-cycle hypothesis, if there are no two disjoint directed cycles, then the set of vertices r ≥ 9 that send an arc to some vertex v < 5 has cardinality at least 4.
digraph_finite_sink_strong_subgraph
Any nonempty finite induced subgraph H of a digraph contains a sink strongly connected component T: a nonempty strongly connected subset such that any out-arc from T into H remains in T.
Finset.mem_filter
An element a belongs to the filtered set {x ∈ s | p x} if and only if a ∈ s and p a holds.
List.isChain_cons_cons
A list a :: b :: l is a directed chain with respect to relation R if and only if R a b holds and b :: l is a directed chain.
Finset.disjoint_left
Two finite sets s and t are disjoint if and only if no element of s belongs to t.
Finset.card_le_card
If a finite set s is a subset of t, then the cardinality of s is at most that of t.
Finset.not_subset
A set s is not a subset of t if and only if there exists some element x ∈ s such that x ∉ t.
digraph_low_cut_contains_cycle_outdeg_cycle
In a loopless digraph on a finite type, any nonempty subset of vertices in which every vertex has at least one out-neighbor inside the subset contains a directed cycle.
Fin.ext
Two elements of a finite type Fin n are equal if and only if their underlying natural number values are equal.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
subset_refl
Every set is a subset of itself.
digraph_common_cycle_core_outside_injection
In a loopless strongly connected digraph component T, if every directed cycle in T contains K, and every vertex of S ⊆ K has out-degree at least 2 in T, then |S| ≤ |T \ K|.
le_trans
Inequality ≤ is transitive: if a ≤ b and b ≤ c, then a ≤ c.
digraph_common_cycle_core_neighbor_unique
In a loopless strongly connected digraph component T where every directed cycle contains S, every vertex in T has at most one out-neighbor and at most one in-neighbor in S.
digraph_common_cycle_core_excludes_high_degree_vertices
In a loopless digraph component T ⊆ R ∪ P with nonempty common cycle core S, if |P| + 2 ≤ k, every vertex in T has at most one out-neighbor in S, and every vertex in T ∩ (R \ S) has out-degree at least k in T, then T is disjoint from R \ S.
Finset.mem_sdiff
An element a belongs to the set difference s \ t if and only if a ∈ s and a ∉ t.

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

theorem digraph_16_shared_target_forces_two_cycles    (D : Digraph (Fin 16)) [DecidableRel D.Adj]    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)    (hdeg : ∀ v : Fin 16, 5 ≤ v.val →      (Finset.univ.filter fun w => D.Adj v w).card = 7)    (hlow : ∀ v : Fin 16, v.val < 5 → D.Adj v 8)    (hout : ∀ v : Fin 16, 9 ≤ v.val → D.Adj 8 v)    (htwo : ∀ T : Finset (Fin 16), T.Nonempty →      (∀ v ∈ T, 3 ≤ (T.filter fun w => D.Adj v w).card) →      ∃ c : Fin 2 → Finset (Fin 16), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j))) :    ∃ c : Fin 2 → Finset (Fin 16),      (∀ i, digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j)) := by  classical  by_contra hno  have hloop : ∀ v, ¬ D.Adj v v := fun v hv => hori v v hv hv  let R : Finset (Fin 16) := Finset.univ.filter fun v => 9 ≤ v.val  let P : Finset (Fin 16) := Finset.univ.filter fun v => 5 ≤ v.val ∧ v.val < 8  let H : Finset (Fin 16) := Finset.univ.filter fun v => 5 ≤ v.val ∧ v.val ≠ 8  let S : Finset (Fin 16) := Finset.univ.filter fun r => 9 ≤ r.val ∧ ∃ v : Fin 16, v.val < 5 ∧ D.Adj r v  have hScard : 4 ≤ S.card :=    digraph_16_shared_target_many_low_arcs D hori (fun v hv => hdeg v (by omega)) hlow hout htwo hno  have hHne : H.Nonempty := ⟨(5 : Fin 16), by decide⟩  obtain ⟨T, hTH, hTne, hsink, hstrong⟩ := digraph_finite_sink_strong_subgraph (Fin 16) D H hHne  have hcore_H (C : Finset (Fin 16)) (hCH : C ⊆ H) (hC : digraph_directed_cycle_on D C) : S ⊆ C := by    intro s hs    rw [Finset.mem_filter] at hs    obtain ⟨-, hsval, v, hvval, hsv⟩ := hs    by_contra hsC    have hv8 : v ≠ (8 : Fin 16) := by intro h; have := congrArg Fin.val h; norm_num at this; omega    have hvs : v ≠ s := by intro h; have := congrArg Fin.val h; omega    have h8s : (8 : Fin 16) ≠ s := by intro h; have := congrArg Fin.val h; norm_num at this; omega    have htri : digraph_directed_cycle_on D ({v,8,s} : Finset (Fin 16)) := by      refine ⟨[v,8,s], ?_, by simp, by simp, ?_, ?_⟩      · simp [hv8,hvs,h8s]      · simpa [List.isChain_cons_cons] using ⟨hlow v hvval, hout s hsval⟩      · exact ⟨v,s,by simp,by simp,hsv⟩    have hdis : Disjoint ({v,8,s} : Finset (Fin 16)) C := by      rw [Finset.disjoint_left]      intro x hx hxC      have hxH : x ∈ H := hCH hxC      rw [Finset.mem_filter] at hxH      simp only [Finset.mem_insert, Finset.mem_singleton] at hx      rcases hx with rfl | rfl | rfl      · omega      · exact hxH.2.2 rfl      · exact hsC hxC    let f : Fin 2 → Finset (Fin 16) := Fin.cases {v,8,s} (fun _ => C)    apply hno    refine ⟨f, ?_, ?_⟩    · intro i      fin_cases i      · exact htri      · exact hC    · intro i j hij      fin_cases i <;> fin_cases j <;>        first | exact (hij rfl).elim | exact hdis | exact hdis.symm  have hsucc : ∀ v ∈ T, ∃ w ∈ T, D.Adj v w := by    intro v hv    have hvH : v ∈ H := hTH hv    rw [Finset.mem_filter] at hvH    let N := Finset.univ.filter fun w => D.Adj v w    have h7 : N.card = 7 := hdeg v hvH.2.1    have hHc : (Hᶜ : Finset (Fin 16)).card = 6 := by decide    have hNne : ¬ (N ⊆ Hᶜ) := by      intro hsub      have := Finset.card_le_card hsub      omega    rw [Finset.not_subset] at hNne    obtain ⟨w, hwN, hwHc⟩ := hNne    rw [Finset.mem_compl] at hwHc    have hwH : w ∈ H := Classical.not_not.mp hwHc    rw [Finset.mem_filter] at hwN    exact ⟨w, hsink v hv w hwH hwN.2, hwN.2⟩  obtain ⟨C, hCT, hC⟩ := digraph_low_cut_contains_cycle_outdeg_cycle (Fin 16) D hloop T hTne hsucc  have hST : S ⊆ T := (hcore_H C (hCT.trans hTH) hC).trans hCT  have hcore_T : ∀ C ⊆ T, digraph_directed_cycle_on D C → S ⊆ C :=    fun C hCsub hCcyc => hcore_H C (hCsub.trans hTH) hCcyc  have hs_deg : ∀ s ∈ S, 2 ≤ (T.filter fun w => D.Adj s w).card := by    intro s hs    have hsT : s ∈ T := hST hs    have hsval : 9 ≤ s.val := (Finset.mem_filter.mp hs).2.1    have hn8 : ¬ D.Adj s 8 := hori 8 s (hout s hsval)    let N := Finset.univ.filter fun w => D.Adj s w    have hNcard : N.card = 7 := hdeg s (by omega)    let L : Finset (Fin 16) := Finset.univ.filter fun w => w.val < 5    have hLcard : L.card = 5 := by decide    let Nc := Hᶜ.filter fun w => D.Adj s w    have hNcsub : Nc ⊆ L := by      intro w hw      have hadj : D.Adj s w := (Finset.mem_filter.mp hw).2      have hnotH : w ∉ H := (Finset.mem_compl.mp (Finset.mem_filter.mp hw).1)      have hwlow : w.val < 5 := by        by_contra hcon        have h5 : 5 ≤ w.val := by omega        have hne8 : w.val ≠ 8 := by          intro heq          have : w = 8 := Fin.ext heq          subst w          exact hn8 hadj        apply hnotH        exact Finset.mem_filter.mpr ⟨Finset.mem_univ w, h5, hne8⟩      exact Finset.mem_filter.mpr ⟨Finset.mem_univ w, hwlow⟩    have hNccard : Nc.card ≤ 5 := by      have := Finset.card_le_card hNcsub      omega    let Nh := H.filter fun w => D.Adj s w    have hNh_eq : Nh = T.filter fun w => D.Adj s w := by      ext w      simp only [Finset.mem_filter, Nh]      constructor      · rintro ⟨hwH, hadj⟩        exact ⟨hsink s hsT w hwH hadj, hadj⟩      · rintro ⟨hwT, hadj⟩        exact ⟨hTH hwT, hadj⟩    have hdecomp : N = Nh ∪ Nc := by      ext w      simp only [N, Nh, Nc, Finset.mem_filter, Finset.mem_union, Finset.mem_compl, Finset.mem_univ, true_and]      by_cases hw : w ∈ H <;> simp [hw]    have hdisj : Disjoint Nh Nc := by      rw [Finset.disjoint_left]      intro x hx1 hx2      have : x ∉ H := Finset.mem_compl.mp (Finset.mem_filter.mp hx2).1      exact this (Finset.mem_filter.mp hx1).1    have hsum : N.card = Nh.card + Nc.card := by      rw [hdecomp, Finset.card_union_of_disjoint hdisj]    rw [hNh_eq] at hsum    omega  have hinj := digraph_common_cycle_core_outside_injection (Fin 16) D T S S hST (subset_refl S) hloop hstrong hcore_T hs_deg  have hdiff4 : 4 ≤ (T \ S).card := le_trans hScard hinj  have hneS : S.Nonempty := Finset.card_pos.mp (by omega)  have hcover : T ⊆ R ∪ P := by    intro x hx    have hxH := hTH hx    rw [Finset.mem_filter] at hxH    rw [Finset.mem_union, Finset.mem_filter, Finset.mem_filter]    by_cases hx8 : x.val < 8    · right      exact ⟨Finset.mem_univ x, hxH.2.1, hx8⟩    · left      have : 9 ≤ x.val := by        have : x.val ≠ 8 := hxH.2.2        omega      exact ⟨Finset.mem_univ x, this⟩  have hPcard : P.card + 2 ≤ 5 := by decide  have huniq (x : Fin 16) (hx : x ∈ T) : (S.filter fun y => D.Adj x y).card ≤ 1 :=    (digraph_common_cycle_core_neighbor_unique (Fin 16) D T S hST hloop hstrong hcore_T x hx).1  have hdeg5 (x : Fin 16) (hxT : x ∈ T) (hxR : x ∈ R) (hxS : x ∉ S) : 5 ≤ (T.filter fun y => D.Adj x y).card := by    have hxval : 9 ≤ x.val := (Finset.mem_filter.mp hxR).2    have hn8 : ¬ D.Adj x 8 := hori 8 x (hout x hxval)    have hnolow : ∀ v : Fin 16, v.val < 5 → ¬ D.Adj x v := by      intro v hv hadj      apply hxS      rw [Finset.mem_filter]      exact ⟨Finset.mem_univ x, hxval, v, hv, hadj⟩    let N := Finset.univ.filter fun w => D.Adj x w    have hNcard : N.card = 7 := hdeg x (by omega)    have hsubH : N ⊆ H := by      intro w hw      rw [Finset.mem_filter] at hw      rw [Finset.mem_filter]      refine ⟨Finset.mem_univ w, ?_, ?_⟩      · by_contra hlt        have : w.val < 5 := by omega        exact hnolow w this hw.2      · intro heq        have : w = 8 := Fin.ext heq        subst w        exact hn8 hw.2    have hsubT : N ⊆ T.filter fun y => D.Adj x y := by      intro w hw      rw [Finset.mem_filter] at hw      have hwH := hsubH (Finset.mem_filter.mpr hw)      exact Finset.mem_filter.mpr ⟨hsink x hxT w hwH hw.2, hw.2⟩    have := Finset.card_le_card hsubT    omega  have hdisj_T_RS : Disjoint T (R \ S) :=    digraph_common_cycle_core_excludes_high_degree_vertices (Fin 16) D T R S P 5 hloop hneS hcover hPcard hcore_T huniq hdeg5  have hsubP : T \ S ⊆ P := by    intro x hx    rw [Finset.mem_sdiff] at hx    have hxT := hx.1    have hxS := hx.2    have hxRP := hcover hxT    rw [Finset.mem_union] at hxRP    rcases hxRP with hxR | hxP    · exfalso      have hxRS : x ∈ R \ S := Finset.mem_sdiff.mpr ⟨hxR, hxS⟩      exact Finset.disjoint_left.mp hdisj_T_RS hxT hxRS    · exact hxP  have hP3 : P.card = 3 := by decide  have hle3 : (T \ S).card ≤ 3 := by    have := Finset.card_le_card hsubP    omega  omega
See it in the graphDiscuss this resultChallenge it