digraph_safe17_two_cycle_impossible
theoremverified
The displayed oriented graph has no directed cycle on two vertices.
Statement
theorem digraph_safe17_two_cycle_impossible
(C : Finset (Fin 17)) (hcycle : digraph_directed_cycle_on digraph_safe17_graph C)
(hcard : C.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_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_safe17_structureThe displayed graph is oriented and seven-diregular, and every two distinct vertices have a common predecessor.
- 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_3 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instanceset_option maxHeartbeats 0set_option maxRecDepth 100000theorem digraph_safe17_two_cycle_impossible (C : Finset (Fin 17)) (hcycle : digraph_directed_cycle_on digraph_safe17_graph C) (hcard : C.card = 2) : False := by obtain ⟨l,hn,hlen0,hset,hchain,hclose⟩ := hcycle have hlen : l.length = 2 := by have h := List.toFinset_card_of_nodup hn rw [hset,hcard] at h omega have hshape : ∃ u a, l = [u,a] := by cases l with | nil => simp at hlen | cons u l => cases l with | nil => simp at hlen | cons a l => cases l with | nil => exact ⟨u,a,rfl⟩ | cons b l => simp at hlen obtain ⟨u,a,rfl⟩ := hshape have hua : digraph_safe17_graph.Adj u a := by simpa [List.isChain_cons_cons] using hchain have hau : digraph_safe17_graph.Adj a u := by obtain ⟨x,y,hx,hy,hxy⟩ := hclose simp only [List.head?_cons, Option.some.injEq] at hx simp at hy subst x subst y exact hxy exact (digraph_safe17_structure.2.1 u a hua) hau