digraph_16_shared_target_many_low_arcs
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
- digraph_16_shared_target_forces_two_cyclesThe normalized oriented sixteen-vertex shared-target configuration contains two disjoint cycles, assuming the displayed two-cycle criterion.
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.
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.
uses
Finset.filter_subsetclassical 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 _ _
|U| + |S| = 7
Because S is a subset of R and U = R \ S, the sizes partition |R|: |U| + |S| = |R| = 7.
uses
Finset.card_sdiff_add_card_eq_cardhave 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
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.
uses
Finset.mem_sdiff.mp,Finset.mem_filter.mprhave 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⟩⟩
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.
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_lehave 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
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.
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_lehave 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
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.
uses
Finset.mem_filterhave 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
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.
uses
Finset.mem_filter.mp,Finset.card_pos.mp,digraph_low_cut_contains_cycle_outdeg_cycleby_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
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}.
uses
congrArg,Fin.val,List.isChain_cons_conshave 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⟩
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.
uses
Finset.disjoint_left.mpr,Finset.mem_sdiff.mp,Finset.mem_filter.mp,Finset.mem_insert,Finset.mem_singleton,Fin.caseshave 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
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.
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.
- The cardinalities of the finite index sets R and P are computed by the decision procedure `decide`.
- Linear inequalities involving set cardinalities are discharged using the integer linear arithmetic solver `omega`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩