digraph_16_shared_target_forces_two_cycles
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
- 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_16_shared_target_many_low_arcsIn the displayed oriented sixteen-vertex configuration with no two disjoint cycles, at least four outneighbors of the common target point…
- digraph_common_cycle_core_neighbor_uniqueInside a strongly connected finite set, if every directed cycle contains a fixed core, every vertex has at most one outgoing neighbor and…
- 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…
- digraph_finite_sink_strong_subgraphEvery nonempty finite vertex set contains a nonempty strongly connected subset with no outgoing arc to the rest of that set.
- digraph_common_cycle_core_excludes_high_degree_verticesSuppose a finite vertex set T is covered by R and P, P has at most k minus two vertices, every directed cycle in T contains a nonempty set…
- digraph_common_cycle_core_outside_injectionIn a strongly connected finite vertex set, suppose all directed cycles contain a core K and every vertex in a subset S of K has at least…
- digraph_is_directed_pathA directed path from u to v in a digraph D is a list of vertices p forming a directed chain in D with no duplicate vertices, starting at u…
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.
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).
uses
digraph_16_shared_target_many_low_arcsclassical 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
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.
uses
digraph_finite_sink_strong_subgraphhave hHne : H.Nonempty := ⟨(5 : Fin 16), by decide⟩ obtain ⟨T, hTH, hTne, hsink, hstrong⟩ := digraph_finite_sink_strong_subgraph (Fin 16) D H hHne
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.
uses
Finset.mem_filter,List.isChain_cons_cons,Finset.disjoint_lefthave 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
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.
uses
Finset.card_le_card,Finset.not_subset,digraph_low_cut_contains_cycle_outdeg_cyclehave 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
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.
uses
Fin.ext,Finset.card_union_of_disjoint,subset_refl,digraph_common_cycle_core_outside_injection,le_transhave 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)
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.
uses
digraph_common_cycle_core_neighbor_uniquehave 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
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.
uses
Fin.ext,digraph_common_cycle_core_excludes_high_degree_verticeshave 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
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.
uses
Finset.mem_sdiff,Finset.card_le_cardhave 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.
- The hypothesis htwo is an assumption that any nonempty induced subgraph with minimum out-degree at least 3 contains two disjoint directed cycles; this condition is supplied as a hypothesis rather than proved internally here.
- Evaluations of cardinalities and inclusions on small finite sets (such as P.card = 3 and the complement of H having 6 vertices) are decided automatically by Lean's decide and omega tactics.
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.
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