AFTD Auto-Formalizing Theoretical Domains

digraph_16_shared_target_many_low_arcs

theoremverified

In the displayed oriented sixteen-vertex configuration with no two disjoint cycles, at least four outneighbors of the common target point to the five low vertices, assuming the displayed two-cycle criterion.

Statement

theorem digraph_16_shared_target_many_low_arcs
    (D : Digraph (Fin 16)) [DecidableRel D.Adj]
    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)
    (hdeg : ∀ v : Fin 16, 9 ≤ 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)))
    (hno : ¬ ∃ c : Fin 2 → Finset (Fin 16),
      (∀ i, digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j))) :
    4 ≤ (Finset.univ.filter fun r : Fin 16 => 9 ≤ r.val ∧
      ∃ v : Fin 16, v.val < 5 ∧ D.Adj r v).card
Source
Analysis of the normalized first equality-profile size for OP-110.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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_low_cut_contains_cycleIn a finite loopless digraph with minimum outdegree at least r, a vertex set of at least r vertices contains a directed cycle if fewer…
Used by 1

The proof, explained

The theorem is proved by contradiction: assuming fewer than 4 of the 7 high vertices (indices 9 to 15) point to the five low vertices (0 to 4), the remaining high vertices U have size at least 4 and must send at least 4 out-arcs back into the high vertices. If any high vertex r points to a low vertex v, the three vertices v, 8, and r form an explicit directed triangle that is disjoint from a directed cycle found in U. If no high vertex points to a low vertex, the entire set of high vertices has minimum out-degree at least 3, which by the assumed two-cycle criterion also yields two disjoint cycles, contradicting the global assumption that no two disjoint cycles exist.

  1. Define vertex sets R (high vertices), S (high vertices pointing to low vertices), U (high vertices with no low out-arcs), and P (middle vertices), and note |R| = 7, |P| = 3, and S ⊆ R

    We partition the sixteen vertices into relevant ranges: R = {v | v ≥ 9} contains the 7 high vertices, S ⊆ R consists of high vertices with an arc to some low vertex v < 5, U = R \ S consists of high vertices with no such arc, and P = {v | 5 ≤ v < 8} contains the 3 middle vertices. Evaluating the set definitions directly yields |R| = 7 and |P| = 3, and S ⊆ R holds by definition of filtering.

    lines 20–27

    uses Finset.filter_subset

      classical
      let R : Finset (Fin 16) := Finset.univ.filter fun v => 9 ≤ v.val
      let S : Finset (Fin 16) := R.filter fun r => ∃ v : Fin 16, v.val < 5 ∧ D.Adj r v
      let U := R \ S
      let P : Finset (Fin 16) := Finset.univ.filter fun v => 5 ≤ v.val ∧ v.val < 8
      have hRcard : R.card = 7 := by decide
      have hPcard : P.card = 3 := by decide
      have hSR : S ⊆ R := Finset.filter_subset _ _
  2. |U| + |S| = 7

    Because S is a subset of R and U = R \ S, the sizes partition |R|: |U| + |S| = |R| = 7.

    lines 28–31

    uses Finset.card_sdiff_add_card_eq_card

      have hUcard : U.card + S.card = 7 := by
        have hh := Finset.card_sdiff_add_card_eq_card hSR
        change U.card + S.card = R.card at hh
        omega
  3. No vertex in U has an out-arc to any low vertex v < 5

    By definition, U = R \ S. Any vertex in R with an arc to a vertex v < 5 would belong to S, which contradicts membership in U.

    lines 32–38

    uses Finset.mem_sdiff.mp, Finset.mem_filter.mpr

      have hno_low (r : Fin 16) (hr : r ∈ U) :
          ∀ v : Fin 16, v.val < 5 → ¬ D.Adj r v := by
        intro v hv hadj
        have hrR : r ∈ R := (Finset.mem_sdiff.mp hr).1
        have hrS : r ∉ S := (Finset.mem_sdiff.mp hr).2
        apply hrS
        exact Finset.mem_filter.mpr ⟨hrR, ⟨v,hv,hadj⟩⟩
  4. Every vertex in U has at least 4 out-neighbors in R (7 ≤ |N⁺(r) ∩ R| + 3)

    Let r ∈ U. Since r ≥ 9, its out-degree in D is 7. No out-neighbor w of r can have w < 5 (as r ∈ U), nor can w equal 8 (since vertex 8 points to r by hypothesis, and D is oriented so r cannot point back to 8). Hence every out-neighbor w must satisfy w ≥ 9 (w ∈ R) or 5 ≤ w < 8 (w ∈ P). Thus N⁺(r) ⊆ (N⁺(r) ∩ R) ∪ P, which gives 7 = |N⁺(r)| ≤ |N⁺(r) ∩ R| + |P| = |N⁺(r) ∩ R| + 3.

    lines 39–66

    uses Finset.mem_sdiff.mp, Finset.mem_filter.mp, Finset.mem_union_left, Finset.mem_filter.mpr, Finset.mem_univ, Fin.ext, Finset.mem_union_right, Finset.card_le_card, Finset.card_union_le

      have hRbound (r : Fin 16) (hr : r ∈ U) :
          7 ≤ (R.filter fun w => D.Adj r w).card + 3 := by
        have hrR : r ∈ R := (Finset.mem_sdiff.mp hr).1
        have hrval : 9 ≤ r.val := (Finset.mem_filter.mp hrR).2
        have hn8 : ¬ D.Adj r 8 := hori 8 r (hout r hrval)
        let I := Finset.univ.filter fun w => D.Adj r w
        let K := R.filter fun w => D.Adj r w
        have hsub : I ⊆ K ∪ P := by
          intro w hw
          have hadj : D.Adj r w := (Finset.mem_filter.mp hw).2
          by_cases hw9 : 9 ≤ w.val
          · apply Finset.mem_union_left
            exact Finset.mem_filter.mpr ⟨Finset.mem_filter.mpr ⟨Finset.mem_univ _,hw9⟩, hadj⟩
          · have hw5 : 5 ≤ w.val := by
              by_contra h
              exact hno_low r hr w (by omega) hadj
            have hw8 : w.val < 8 := by
              by_contra h
              have heq : w = (8 : Fin 16) := Fin.ext (by omega)
              subst w
              exact hn8 hadj
            apply Finset.mem_union_right
            exact Finset.mem_filter.mpr ⟨Finset.mem_univ _,hw5,hw8⟩
        have h1 := Finset.card_le_card hsub
        have h2 := Finset.card_union_le K P
        have hI : I.card = 7 := hdeg r hrval
        change 7 ≤ K.card + 3
        omega
  5. Every vertex in U satisfies 7 ≤ |N⁺(r) ∩ U| + |S| + 3

    For r ∈ U, any out-neighbor of r in R lies either in U = R \ S or in S, so N⁺(r) ∩ R ⊆ (N⁺(r) ∩ U) ∪ S. Combining this with 7 ≤ |N⁺(r) ∩ R| + 3 yields 7 ≤ |N⁺(r) ∩ U| + |S| + 3.

    lines 67–84

    uses Finset.mem_filter.mp, Finset.mem_union_right, Finset.mem_union_left, Finset.mem_filter.mpr, Finset.mem_sdiff.mpr, Finset.card_le_card, Finset.card_union_le

      have hUbound (r : Fin 16) (hr : r ∈ U) :
          7 ≤ (U.filter fun w => D.Adj r w).card + S.card + 3 := by
        let K := R.filter fun w => D.Adj r w
        let L := U.filter fun w => D.Adj r w
        have hsub : K ⊆ L ∪ S := by
          intro w hw
          have hwR : w ∈ R := (Finset.mem_filter.mp hw).1
          have hadj : D.Adj r w := (Finset.mem_filter.mp hw).2
          by_cases hwS : w ∈ S
          · exact Finset.mem_union_right L hwS
          · apply Finset.mem_union_left
            exact Finset.mem_filter.mpr ⟨Finset.mem_sdiff.mpr ⟨hwR,hwS⟩,hadj⟩
        have h1 := Finset.card_le_card hsub
        have h2 := Finset.card_union_le L S
        have h3 := hRbound r hr
        change 7 ≤ K.card + 3 at h3
        change 7 ≤ L.card + S.card + 3
        omega
  6. It suffices to assume for contradiction that |S| ≤ 3

    The goal is to show that at least 4 high vertices point to low vertices, which is precisely 4 ≤ |S|. We proceed by contradiction, assuming |S| ≤ 3.

    lines 85–91

    uses Finset.mem_filter

      have hSeq : S = Finset.univ.filter (fun r => 9 ≤ r.val ∧
          ∃ v : Fin 16, v.val < 5 ∧ D.Adj r v) := by
        ext r
        simp [S,R,Finset.mem_filter]
      rw [← hSeq]
      by_contra hh
      have hsle : S.card ≤ 3 := by omega
  7. If S is nonempty, then U contains a directed cycle C

    Assume S is nonempty. Since |S| ≤ 3 and |U| + |S| = 7, we have |U| ≥ 4, so U is nonempty. For each x ∈ U, the inequality 7 ≤ |N⁺(x) ∩ U| + |S| + 3 combined with |S| ≤ 3 ensures that x has out-degree at least 1 in U. Because D is oriented, it has no self-loops; therefore, by digraph_low_cut_contains_cycle_outdeg_cycle, the set U contains a directed cycle C.

    lines 92–109

    uses Finset.mem_filter.mp, Finset.card_pos.mp, digraph_low_cut_contains_cycle_outdeg_cycle

      by_cases hS : S.Nonempty
      · obtain ⟨r,hr⟩ := hS
        obtain ⟨hrR, v,hvval,hrv⟩ := Finset.mem_filter.mp hr
        have hrval : 9 ≤ r.val := (Finset.mem_filter.mp hrR).2
        have hUne : U.Nonempty := Finset.card_pos.mp (by omega)
        have hUdeg : ∀ x ∈ U, 1 ≤ (U.filter fun w => D.Adj x w).card := by
          intro x hx
          have hh := hUbound x hx
          omega
        have hloop : ∀ x, ¬ D.Adj x x := by
          intro x hx
          exact (hori x x hx) hx
        have hsuccessor : ∀ x ∈ U, ∃ w ∈ U, D.Adj x w := by
          intro x hx
          have hc := hUdeg x hx
          obtain ⟨w,hw⟩ := Finset.card_pos.mp (by omega : 0 < (U.filter fun w => D.Adj x w).card)
          exact ⟨w,(Finset.mem_filter.mp hw).1,(Finset.mem_filter.mp hw).2⟩
        obtain ⟨C,hCU,hC⟩ := digraph_low_cut_contains_cycle_outdeg_cycle (Fin 16) D hloop U hUne hsuccessor
  8. Any r ∈ S and low witness v form a directed 3-cycle on {v, 8, r}

    Pick r ∈ S and a low vertex v < 5 with r → v. The vertices v, 8, and r are distinct because v < 5 < 8 ≤ 9 ≤ r. The hypotheses guarantee v → 8 (as v < 5) and 8 → r (as r ≥ 9), which with r → v forms a directed triangle v → 8 → r → v on {v, 8, r}.

    lines 110–117

    uses congrArg, Fin.val, List.isChain_cons_cons

        have hv8 : v ≠ (8 : Fin 16) := by intro h; have := congrArg Fin.val h; norm_num at this; omega
        have hvr : v ≠ r := by intro h; have := congrArg Fin.val h; omega
        have h8r : (8 : Fin 16) ≠ r := by intro h; have := congrArg Fin.val h; norm_num at this; omega
        have htri : digraph_directed_cycle_on D ({v,8,r} : Finset (Fin 16)) := by
          refine ⟨[v,8,r], ?_, by simp, by simp, ?_, ?_⟩
          · simp [hv8,hvr,h8r]
          · simpa [List.isChain_cons_cons] using ⟨hlow v hvval,hout r hrval⟩
          · exact ⟨v,r,by simp,by simp,hrv⟩
  9. The triangle {v, 8, r} and the cycle C are vertex-disjoint, contradicting the absence of two disjoint cycles

    All vertices of C lie in U = R \ S, meaning they have index at least 9 and do not belong to S. Thus C cannot contain v (< 5), 8, or r (which is in S). The triangle and C are therefore disjoint directed cycles, contradicting the hypothesis hno.

    lines 118–138

    uses Finset.disjoint_left.mpr, Finset.mem_sdiff.mp, Finset.mem_filter.mp, Finset.mem_insert, Finset.mem_singleton, Fin.cases

        have hdis : Disjoint ({v,8,r} : Finset (Fin 16)) C := by
          apply Finset.disjoint_left.mpr
          intro x hx hxc
          have hxU : x ∈ U := hCU hxc
          have hxR : x ∈ R := (Finset.mem_sdiff.mp hxU).1
          have hxval : 9 ≤ x.val := (Finset.mem_filter.mp hxR).2
          simp only [Finset.mem_insert, Finset.mem_singleton] at hx
          rcases hx with rfl | rfl | rfl
          · omega
          · norm_num at hxval
          · exact (Finset.mem_sdiff.mp hxU).2 hr
        let f : Fin 2 → Finset (Fin 16) := Fin.cases {v,8,r} (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
  10. If S is empty, R satisfies the two-cycle criterion, also contradicting hno

    If S is empty, then U = R, so |R| = 7 > 0. Every vertex r ∈ R = U has out-degree in R at least 7 - 3 = 4 ≥ 3. Applying the hypothesis htwo to the nonempty set R produces two disjoint directed cycles in R, which again contradicts hno.

    lines 139–148

    uses Finset.not_nonempty_iff_eq_empty.mp, Finset.card_pos.mp

      · have hS0 : S = ∅ := Finset.not_nonempty_iff_eq_empty.mp hS
        have hRne : R.Nonempty := Finset.card_pos.mp (by omega)
        have hRdeg : ∀ r ∈ R, 3 ≤ (R.filter fun w => D.Adj r w).card := by
          intro r hr
          have hrU : r ∈ U := by simpa [U,hS0] using hr
          have hh := hRbound r hrU
          omega
        obtain ⟨c,hc,hdis⟩ := htwo R hRne hRdeg
        apply hno
        exact ⟨c,fun i => (hc i).2,hdis⟩
Fin.val
The underlying natural number value of an element of Fin n.
Fin.ext
Two elements of Fin n are equal if their underlying natural number values are equal.
Fin.cases
Case analysis for Fin (n + 1), evaluating on 0 and on successors.
congrArg
Applying a function to equal values yields equal results.
Finset.filter_subset
Filtering a finite set by a predicate produces a subset of the original set.
Finset.card_sdiff_add_card_eq_card
For finite sets s ⊆ t, the cardinality of the difference t \ s plus the cardinality of s equals the cardinality of t.
Finset.mem_sdiff.mp
If an element belongs to the set difference t \ s, then it belongs to t and not to s.
Finset.mem_sdiff.mpr
If an element belongs to t and not to s, then it belongs to t \ s.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_filter.mpr
If an element is in the base set and satisfies the predicate, it belongs to the filtered set.
Finset.mem_filter.mp
If an element belongs to a filtered set, then it belongs to the base set and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal set Finset.univ.
Finset.mem_union_left
If an element belongs to s, then it belongs to the union s ∪ t.
Finset.mem_union_right
If an element belongs to t, then it belongs to the union s ∪ t.
Finset.card_le_card
If s ⊆ t, then |s| ≤ |t|.
Finset.card_union_le
The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.not_nonempty_iff_eq_empty.mp
If a finite set is not nonempty, then it is empty.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first set belongs to the second set.
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.isChain_cons_cons
A list starting with a and b is a chain under a binary relation if and only if the relation holds between a and b and the tail starting at b is a chain.
digraph_low_cut_contains_cycle_outdeg_cycle
In a finite directed graph with no self-loops, any nonempty subset of vertices in which every vertex has an out-neighbor in the subset contains a directed cycle.

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

set_option maxHeartbeats 3000000set_option maxRecDepth 4096theorem digraph_16_shared_target_many_low_arcs    (D : Digraph (Fin 16)) [DecidableRel D.Adj]    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)    (hdeg : ∀ v : Fin 16, 9 ≤ 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)))    (hno : ¬ ∃ c : Fin 2 → Finset (Fin 16),      (∀ i, digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j))) :    4 ≤ (Finset.univ.filter fun r : Fin 16 => 9 ≤ r.val ∧      ∃ v : Fin 16, v.val < 5 ∧ D.Adj r v).card := by  classical  let R : Finset (Fin 16) := Finset.univ.filter fun v => 9 ≤ v.val  let S : Finset (Fin 16) := R.filter fun r => ∃ v : Fin 16, v.val < 5 ∧ D.Adj r v  let U := R \ S  let P : Finset (Fin 16) := Finset.univ.filter fun v => 5 ≤ v.val ∧ v.val < 8  have hRcard : R.card = 7 := by decide  have hPcard : P.card = 3 := by decide  have hSR : S ⊆ R := Finset.filter_subset _ _  have hUcard : U.card + S.card = 7 := by    have hh := Finset.card_sdiff_add_card_eq_card hSR    change U.card + S.card = R.card at hh    omega  have hno_low (r : Fin 16) (hr : r ∈ U) :      ∀ v : Fin 16, v.val < 5 → ¬ D.Adj r v := by    intro v hv hadj    have hrR : r ∈ R := (Finset.mem_sdiff.mp hr).1    have hrS : r ∉ S := (Finset.mem_sdiff.mp hr).2    apply hrS    exact Finset.mem_filter.mpr ⟨hrR, ⟨v,hv,hadj⟩⟩  have hRbound (r : Fin 16) (hr : r ∈ U) :      7 ≤ (R.filter fun w => D.Adj r w).card + 3 := by    have hrR : r ∈ R := (Finset.mem_sdiff.mp hr).1    have hrval : 9 ≤ r.val := (Finset.mem_filter.mp hrR).2    have hn8 : ¬ D.Adj r 8 := hori 8 r (hout r hrval)    let I := Finset.univ.filter fun w => D.Adj r w    let K := R.filter fun w => D.Adj r w    have hsub : I ⊆ K ∪ P := by      intro w hw      have hadj : D.Adj r w := (Finset.mem_filter.mp hw).2      by_cases hw9 : 9 ≤ w.val      · apply Finset.mem_union_left        exact Finset.mem_filter.mpr ⟨Finset.mem_filter.mpr ⟨Finset.mem_univ _,hw9⟩, hadj⟩      · have hw5 : 5 ≤ w.val := by          by_contra h          exact hno_low r hr w (by omega) hadj        have hw8 : w.val < 8 := by          by_contra h          have heq : w = (8 : Fin 16) := Fin.ext (by omega)          subst w          exact hn8 hadj        apply Finset.mem_union_right        exact Finset.mem_filter.mpr ⟨Finset.mem_univ _,hw5,hw8⟩    have h1 := Finset.card_le_card hsub    have h2 := Finset.card_union_le K P    have hI : I.card = 7 := hdeg r hrval    change 7 ≤ K.card + 3    omega  have hUbound (r : Fin 16) (hr : r ∈ U) :      7 ≤ (U.filter fun w => D.Adj r w).card + S.card + 3 := by    let K := R.filter fun w => D.Adj r w    let L := U.filter fun w => D.Adj r w    have hsub : K ⊆ L ∪ S := by      intro w hw      have hwR : w ∈ R := (Finset.mem_filter.mp hw).1      have hadj : D.Adj r w := (Finset.mem_filter.mp hw).2      by_cases hwS : w ∈ S      · exact Finset.mem_union_right L hwS      · apply Finset.mem_union_left        exact Finset.mem_filter.mpr ⟨Finset.mem_sdiff.mpr ⟨hwR,hwS⟩,hadj⟩    have h1 := Finset.card_le_card hsub    have h2 := Finset.card_union_le L S    have h3 := hRbound r hr    change 7 ≤ K.card + 3 at h3    change 7 ≤ L.card + S.card + 3    omega  have hSeq : S = Finset.univ.filter (fun r => 9 ≤ r.val ∧      ∃ v : Fin 16, v.val < 5 ∧ D.Adj r v) := by    ext r    simp [S,R,Finset.mem_filter]  rw [← hSeq]  by_contra hh  have hsle : S.card ≤ 3 := by omega  by_cases hS : S.Nonempty  · obtain ⟨r,hr⟩ := hS    obtain ⟨hrR, v,hvval,hrv⟩ := Finset.mem_filter.mp hr    have hrval : 9 ≤ r.val := (Finset.mem_filter.mp hrR).2    have hUne : U.Nonempty := Finset.card_pos.mp (by omega)    have hUdeg : ∀ x ∈ U, 1 ≤ (U.filter fun w => D.Adj x w).card := by      intro x hx      have hh := hUbound x hx      omega    have hloop : ∀ x, ¬ D.Adj x x := by      intro x hx      exact (hori x x hx) hx    have hsuccessor : ∀ x ∈ U, ∃ w ∈ U, D.Adj x w := by      intro x hx      have hc := hUdeg x hx      obtain ⟨w,hw⟩ := Finset.card_pos.mp (by omega : 0 < (U.filter fun w => D.Adj x w).card)      exact ⟨w,(Finset.mem_filter.mp hw).1,(Finset.mem_filter.mp hw).2⟩    obtain ⟨C,hCU,hC⟩ := digraph_low_cut_contains_cycle_outdeg_cycle (Fin 16) D hloop U hUne hsuccessor    have hv8 : v ≠ (8 : Fin 16) := by intro h; have := congrArg Fin.val h; norm_num at this; omega    have hvr : v ≠ r := by intro h; have := congrArg Fin.val h; omega    have h8r : (8 : Fin 16) ≠ r := by intro h; have := congrArg Fin.val h; norm_num at this; omega    have htri : digraph_directed_cycle_on D ({v,8,r} : Finset (Fin 16)) := by      refine ⟨[v,8,r], ?_, by simp, by simp, ?_, ?_⟩      · simp [hv8,hvr,h8r]      · simpa [List.isChain_cons_cons] using ⟨hlow v hvval,hout r hrval⟩      · exact ⟨v,r,by simp,by simp,hrv⟩    have hdis : Disjoint ({v,8,r} : Finset (Fin 16)) C := by      apply Finset.disjoint_left.mpr      intro x hx hxc      have hxU : x ∈ U := hCU hxc      have hxR : x ∈ R := (Finset.mem_sdiff.mp hxU).1      have hxval : 9 ≤ x.val := (Finset.mem_filter.mp hxR).2      simp only [Finset.mem_insert, Finset.mem_singleton] at hx      rcases hx with rfl | rfl | rfl      · omega      · norm_num at hxval      · exact (Finset.mem_sdiff.mp hxU).2 hr    let f : Fin 2 → Finset (Fin 16) := Fin.cases {v,8,r} (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 hS0 : S = ∅ := Finset.not_nonempty_iff_eq_empty.mp hS    have hRne : R.Nonempty := Finset.card_pos.mp (by omega)    have hRdeg : ∀ r ∈ R, 3 ≤ (R.filter fun w => D.Adj r w).card := by      intro r hr      have hrU : r ∈ U := by simpa [U,hS0] using hr      have hh := hRbound r hrU      omega    obtain ⟨c,hc,hdis⟩ := htwo R hRne hRdeg    apply hno    exact ⟨c,fun i => (hc i).2,hdis⟩
See it in the graphDiscuss this resultChallenge it