digraph_safe17_triangle_unsafe
Every directed triangle in the displayed graph has an outside vertex pointing to all three of its vertices.
Statement
theorem digraph_safe17_triangle_unsafe (u a b : Fin 17)
(hua : digraph_safe17_graph.Adj u a) (hab : digraph_safe17_graph.Adj a b)
(hbu : digraph_safe17_graph.Adj b u) :
∃ x : Fin 17, x ≠ u ∧ x ≠ a ∧ x ≠ b ∧
digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧
digraph_safe17_graph.Adj x b- 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_triangle_unsafeEvery directed triangle through zero in the displayed graph has an outside vertex pointing to all three of its vertices.
- Used by 2
- digraph_safe17_triangle_cycle_unsafeNo directed triangle 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
To show that every directed triangle (u, a, b) has an outside common predecessor, the proof translates the triangle by -u so that u becomes 0. It then invokes the rooted case `digraph_safe17_rooted_triangle_unsafe`, which provides an outside common predecessor x for the translated triangle (0, a - u, b - u). Finally, shifting x back by +u yields the required vertex x + u pointing to u, a, and b.
Adjacency in the graph is decidable. automation
Given any two vertices u and v, unfolding the definition of the graph shows adjacency is membership in a finite set, which is decidable by typeclass synthesis.
private instance in504_safe17_decAdj_5 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instance
Translating both vertices by -u preserves adjacency: Adj (x - u) (y - u) ↔ Adj x y.
Using the translation invariance of the graph (`digraph_safe17_shift`) by the offset -u and rewriting subtraction as addition of the negative, we establish that shifting by -u preserves adjacency.
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 translated vertices 0, a - u, and b - u form a directed triangle.
Applying the shift equivalence to the original edges u → a, a → b, and b → u shows that 0 → a - u, a - u → b - u, and b - u → 0, forming a directed triangle containing 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 : digraph_safe17_graph.Adj (b-u) 0 := by simpa using (hn b u).2 hbu
There exists a common predecessor x for the shifted triangle (0, a - u, b - u).
By `digraph_safe17_rooted_triangle_unsafe`, any directed triangle containing 0 has an outside vertex x pointing to all three vertices 0, a - u, and b - u.
uses
digraph_safe17_rooted_triangle_unsafeobtain ⟨x,hx0,hxa,hxb,hu,ha,hb⟩ := digraph_safe17_rooted_triangle_unsafe (a-u) (b-u) h1 h2 h3If x is distinct from v - u, then x + u is distinct from v.
Assuming x + u = v, subtracting u from both sides via `congrArg` would give x = v - u, contradicting the assumption that x ≠ v - 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
If x points to v - u, then x + u points to v.
Shifting the edge from x to v - u by +u via `digraph_safe17_shift` gives an edge from x + u to (v - u) + u = v.
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
The vertex x + u is the desired outside vertex pointing to u, a, and b.
We instantiate the existential witness with x + u. Since x is distinct from 0, a - u, and b - u, x + u is distinct from u, a, and b. Moreover, shifting the edges x → a - u and x → b - u gives edges x + u → a and x + u → b, and shifting x → 0 gives an edge x + u → u.
uses
digraph_safe17_shiftrefine ⟨x+u,hne u (by simpa using hx0),hne a hxa,hne b hxb,?_,back a ha,back b hb⟩ simpa using (digraph_safe17_shift x 0 u).2 hu
sub_eq_add_neg- Subtracting an element equals adding its additive inverse.
digraph_safe17_shift- Shifting both vertices by any offset t preserves directed adjacency in this circulant graph.
digraph_safe17_rooted_triangle_unsafe- Every directed triangle with one vertex at 0 has a common outside predecessor.
congrArg- Functions preserve equality: if x = y, then f(x) = f(y).
- Lines 1–4 provide a decidability instance for adjacency, which is required by Lean's typeclass resolution for finite checks.
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_5 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instancetheorem digraph_safe17_triangle_unsafe (u a b : Fin 17) (hua : digraph_safe17_graph.Adj u a) (hab : digraph_safe17_graph.Adj a b) (hbu : digraph_safe17_graph.Adj b u) : ∃ x : Fin 17, x ≠ u ∧ x ≠ a ∧ x ≠ b ∧ digraph_safe17_graph.Adj x u ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b := 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 : digraph_safe17_graph.Adj (b-u) 0 := by simpa using (hn b u).2 hbu obtain ⟨x,hx0,hxa,hxb,hu,ha,hb⟩ := digraph_safe17_rooted_triangle_unsafe (a-u) (b-u) h1 h2 h3 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 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 refine ⟨x+u,hne u (by simpa using hx0),hne a hxa,hne b hxb,?_,back a ha,back b hb⟩ simpa using (digraph_safe17_shift x 0 u).2 hu