digraph_safe17_four_unsafe
Every directed four-cycle in the displayed graph has an outside vertex pointing to at least three of its vertices.
Statement
theorem digraph_safe17_four_unsafe (u a b c : Fin 17)
(hua : digraph_safe17_graph.Adj u a) (hab : digraph_safe17_graph.Adj a b)
(hbc : digraph_safe17_graph.Adj b c) (hcu : digraph_safe17_graph.Adj c u) :
∃ x : Fin 17, x ≠ u ∧ x ≠ a ∧ x ≠ b ∧ x ≠ c ∧
((digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b) ∨
(digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x c) ∨
(digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x b ∧ digraph_safe17_graph.Adj x c) ∨
(digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b ∧ digraph_safe17_graph.Adj x c))- Source
- Finite 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_shiftThe displayed cyclic graph is invariant under translating both endpoints.
- digraph_safe17_rooted_four_unsafeEvery directed four-cycle through zero in the displayed graph has an outside vertex pointing to at least three of its vertices.
- Used by 2
- digraph_safe17_four_cycle_unsafeNo directed four-cycle in the displayed graph is safe for deletion with a two-neighbor budget.
- 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.
The proof, explained
The proof reduces the existence of a dominating outside vertex for an arbitrary directed 4-cycle $u \to a \to b \to c \to u$ to the rooted case where one vertex is 0, by translating all vertices by $-u$. Because edge adjacency on $\mathbb{Z}/17\mathbb{Z}$ is translation-invariant, the shifted cycle forms a valid 4-cycle rooted at 0, allowing us to invoke digraph_safe17_rooted_four_unsafe to obtain a witness $x$. Finally, translating $x$ back to $x+u$ preserves both its distinctness from the cycle vertices and all directed edges, producing the desired outside vertex for the original cycle.
Adjacency in the graph is decidable.
By unfolding the definition of adjacency in digraph_safe17_graph, whether an edge exists between $u$ and $v$ reduces to checking whether $(v-u).val$ belongs to a specific finite set of natural numbers, which Lean infers automatically as a decidable relation.
private instance in504_safe17_decAdj_6 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instance
Adjacency is invariant under subtracting $u$: $x - u \to y - u$ if and only if $x \to y$.
Shifting both vertices by $-u$ preserves adjacency by digraph_safe17_shift, and rewriting subtraction as addition of the negation via sub_eq_add_neg simplifies $(x + -u)$ and $(y + -u)$ to $x - u$ and $y - u$.
uses
sub_eq_add_neg,digraph_safe17_shifthave hn (x y : Fin 17) : digraph_safe17_graph.Adj (x-u) (y-u) ↔ digraph_safe17_graph.Adj x y := by simpa only [sub_eq_add_neg] using digraph_safe17_shift x y (-u)
The shifted vertices $0, a-u, b-u, c-u$ form a directed 4-cycle rooted at 0.
Applying shift-invariance (hn) to each of the four edges $u \to a$, $a \to b$, $b \to c$, and $c \to u$, and noting that $u - u = 0$, yields edges $0 \to a-u$, $a-u \to b-u$, $b-u \to c-u$, and $c-u \to 0$.
have h1 : digraph_safe17_graph.Adj 0 (a-u) := by simpa using (hn u a).2 hua have h2 := (hn a b).2 hab have h3 := (hn b c).2 hbc have h4 : digraph_safe17_graph.Adj (c-u) 0 := by simpa using (hn c u).2 hcu
There exists a vertex $x \in \mathbb{Z}/17\mathbb{Z}$ outside the shifted 4-cycle that points to at least three of its vertices.
We apply digraph_safe17_rooted_four_unsafe to the shifted 4-cycle $0 \to a-u \to b-u \to c-u \to 0$, obtaining an outside vertex $x$ (distinct from $0, a-u, b-u, c-u$) that has edges to at least three of those four vertices.
uses
digraph_safe17_rooted_four_unsafeobtain ⟨x,hx0,hxa,hxb,hxc,htrip⟩ := digraph_safe17_rooted_four_unsafe (a-u) (b-u) (c-u) h1 h2 h3 h4Translating $x$ back by adding $u$ preserves distinctness from the cycle vertices: $x + u \neq u, a, b, c$.
We establish the helper lemma hne: if $x + u = v$, subtracting $u$ from both sides using congrArg would give $x = v - u$, contradicting $x \neq v - u$. Applying this with $v = u$ and using $x \neq 0$ proves $x + u \neq u$.
uses
congrArghave hne (v : Fin 17) (hv : x ≠ v-u) : x+u ≠ v := by intro he apply hv have ht := congrArg (fun z : Fin 17 => z-u) he simpa using ht have hxu : x+u ≠ u := hne u (by simpa using hx0)
Edges from $x$ in the shifted cycle translate back to edges from $x+u$: $x \to v-u$ implies $x+u \to v$, and $x \to 0$ implies $x+u \to u$.
Applying digraph_safe17_shift by adding $u$ maps the edge $x \to v-u$ to $(x+u) \to (v-u+u) = v$, and maps $x \to 0$ to $(x+u) \to u$.
uses
digraph_safe17_shifthave back (v : Fin 17) (hv : digraph_safe17_graph.Adj x (v-u)) : digraph_safe17_graph.Adj (x+u) v := by simpa using (digraph_safe17_shift x (v-u) u).2 hv have back0 (hv : digraph_safe17_graph.Adj x 0) : digraph_safe17_graph.Adj (x+u) u := by simpa using (digraph_safe17_shift x 0 u).2 hv
The translated vertex $x+u$ is an outside vertex pointing to at least three vertices of the original cycle $u, a, b, c$.
We provide $x+u$ as the witness. Its distinctness from $u, a, b, c$ follows from the previous step. We then perform a case analysis on the four possible 3-subsets dominated by $x$ in the shifted cycle; in each case, the back-translation lemmas yield the three corresponding edges from $x+u$ to the vertices in the original cycle.
uses
Or.inl,Or.inrrefine ⟨x+u,hxu,hne a hxa,hne b hxb,hne c hxc,?_⟩ rcases htrip with h | h | h | h · exact Or.inl ⟨back0 h.1,back a h.2.1,back b h.2.2⟩ · exact Or.inr (Or.inl ⟨back0 h.1,back a h.2.1,back c h.2.2⟩) · exact Or.inr (Or.inr (Or.inl ⟨back0 h.1,back b h.2.1,back c h.2.2⟩)) · exact Or.inr (Or.inr (Or.inr ⟨back a h.1,back b h.2.1,back c h.2.2⟩))
sub_eq_add_neg- In a subtraction-negation monoid, subtracting $b$ is equal to adding the negative of $b$: $a - b = a + (-b)$.
digraph_safe17_shift- In the graph, adjacency is invariant under translation by any element $t$: there is an edge $(a+t) \to (b+t)$ if and only if there is an edge $a \to b$.
digraph_safe17_rooted_four_unsafe- Every directed 4-cycle rooted at 0 ($0 \to a \to b \to c \to 0$) in the graph has an outside vertex pointing to at least three of its vertices.
congrArg- Applying a function to equal inputs yields equal outputs: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
Or.inl- Constructs a proof of a disjunction $A \lor B$ from a proof of the left disjunct $A$.
Or.inr- Constructs a proof of a disjunction $A \lor B$ from a proof of the right disjunct $B$.
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.
private instance in504_safe17_decAdj_6 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instancetheorem digraph_safe17_four_unsafe (u a b c : Fin 17) (hua : digraph_safe17_graph.Adj u a) (hab : digraph_safe17_graph.Adj a b) (hbc : digraph_safe17_graph.Adj b c) (hcu : digraph_safe17_graph.Adj c u) : ∃ x : Fin 17, x ≠ u ∧ x ≠ a ∧ x ≠ b ∧ x ≠ c ∧ ((digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b) ∨ (digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x c) ∨ (digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x b ∧ digraph_safe17_graph.Adj x c) ∨ (digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b ∧ digraph_safe17_graph.Adj x c)) := by have hn (x y : Fin 17) : digraph_safe17_graph.Adj (x-u) (y-u) ↔ digraph_safe17_graph.Adj x y := by simpa only [sub_eq_add_neg] using digraph_safe17_shift x y (-u) have h1 : digraph_safe17_graph.Adj 0 (a-u) := by simpa using (hn u a).2 hua have h2 := (hn a b).2 hab have h3 := (hn b c).2 hbc have h4 : digraph_safe17_graph.Adj (c-u) 0 := by simpa using (hn c u).2 hcu obtain ⟨x,hx0,hxa,hxb,hxc,htrip⟩ := digraph_safe17_rooted_four_unsafe (a-u) (b-u) (c-u) h1 h2 h3 h4 have hne (v : Fin 17) (hv : x ≠ v-u) : x+u ≠ v := by intro he apply hv have ht := congrArg (fun z : Fin 17 => z-u) he simpa using ht have hxu : x+u ≠ u := hne u (by simpa using hx0) have back (v : Fin 17) (hv : digraph_safe17_graph.Adj x (v-u)) : digraph_safe17_graph.Adj (x+u) v := by simpa using (digraph_safe17_shift x (v-u) u).2 hv have back0 (hv : digraph_safe17_graph.Adj x 0) : digraph_safe17_graph.Adj (x+u) u := by simpa using (digraph_safe17_shift x 0 u).2 hv refine ⟨x+u,hxu,hne a hxa,hne b hxb,hne c hxc,?_⟩ rcases htrip with h | h | h | h · exact Or.inl ⟨back0 h.1,back a h.2.1,back b h.2.2⟩ · exact Or.inr (Or.inl ⟨back0 h.1,back a h.2.1,back c h.2.2⟩) · exact Or.inr (Or.inr (Or.inl ⟨back0 h.1,back b h.2.1,back c h.2.2⟩)) · exact Or.inr (Or.inr (Or.inr ⟨back a h.1,back b h.2.1,back c h.2.2⟩))