digraph_safe17_no_long_safe_set
theoremverified
Every proper set of at least five vertices in the displayed graph has an outside vertex with at least three outneighbors in the set.
Statement
theorem digraph_safe17_no_long_safe_set (C : Finset (Fin 17)) (hne : ∃ v, v ∉ C) (hlarge : 5 ≤ C.card) (hsafe : ∀ v ∉ C, (C.filter fun w => digraph_safe17_graph.Adj v w).card ≤ 2) : False
- Source
- Safe-cycle obstruction for OP-110; experiment 13260.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- digraph_safe17_graphThe seventeen-vertex cyclic digraph with the displayed seven out-steps.
- digraph_safe17_structureThe displayed graph is oriented and seven-diregular, and every two distinct vertices have a common predecessor.
- digraph_oriented_safe_set_indegree_boundIn a finite loopless oriented digraph of minimum indegree r, a set to which each outside vertex sends at most two arcs satisfies r times…
- Used by 1
- digraph_safe17_every_proper_cycle_unsafeEvery proper directed cycle in the displayed seventeen-vertex graph has an outside vertex with at least three outneighbors on it.
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.
private instance in504_safe17_final_decAdj_0 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instanceset_option maxHeartbeats 0set_option maxRecDepth 100000theorem digraph_safe17_no_long_safe_set (C : Finset (Fin 17)) (hne : ∃ v, v ∉ C) (hlarge : 5 ≤ C.card) (hsafe : ∀ v ∉ C, (C.filter fun w => digraph_safe17_graph.Adj v w).card ≤ 2) : False := by classical obtain ⟨hloop,hori,hout,hin,hcommon⟩ := digraph_safe17_structure have hc : C.card ≤ 17 := by have h := Finset.card_le_card (Finset.subset_univ C) simpa using h have hcount := digraph_oriented_safe_set_indegree_bound (Fin 17) digraph_safe17_graph hloop hori 7 (fun v => (hin v).ge) C hsafe have hbound : 7 * C.card ≤ Nat.choose C.card 2 + 2 * (17-C.card) := by simpa using hcount by_cases hsmall : C.card ≤ 14 · interval_cases h : C.card <;> norm_num [h, Nat.choose] at hbound · have hcard : 15 ≤ C.card := by omega obtain ⟨v,hv⟩ := hne let U : Finset (Fin 17) := Finset.univ \ C have hvU : v ∈ U := by simp [U,hv] have hUcard : U.card = 17-C.card := by simp [U, Finset.card_sdiff] have herase : (U.erase v).card ≤ 1 := by rw [Finset.card_erase_of_mem hvU] omega have hsub : (Finset.univ.filter fun w => digraph_safe17_graph.Adj v w) ⊆ (C.filter fun w => digraph_safe17_graph.Adj v w) ∪ U.erase v := by intro w hw have hadj := (Finset.mem_filter.mp hw).2 by_cases hwC : w ∈ C · exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwC,hadj⟩) · have hwu : w ≠ v := by intro h; subst w; exact hloop v hadj apply Finset.mem_union_right simp [U,hwC,hwu] have hcount := Finset.card_le_card hsub have hunion := Finset.card_union_le (C.filter fun w => digraph_safe17_graph.Adj v w) (U.erase v) have hsafe' := hsafe v hv have hd := hout v omega