digraph_safe17_triangle_cycle_unsafe
No directed triangle in the displayed graph is safe for deletion with a two-neighbor budget.
Statement
theorem digraph_safe17_triangle_cycle_unsafe (C : Finset (Fin 17)) (hcycle : digraph_directed_cycle_on digraph_safe17_graph C) (hcard : C.card = 3) (hsafe : ∀ x ∉ C, (C.filter fun w => digraph_safe17_graph.Adj x w).card ≤ 2) : False
- Source
- Safe-cycle obstruction for OP-110; experiment 13260.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_triangle_unsafeEvery directed triangle in the displayed graph has an outside vertex pointing to all three of its vertices.
- digraph_safe17_three_neighbors_not_safeAn outside vertex pointing to three distinct vertices in a set violates the displayed two-neighbor safety condition.
- 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.
The proof, explained
Any directed cycle of size 3 in the graph must consist of three distinct vertices forming a directed triangle. By a previously established graph property, every directed triangle has an external vertex with directed edges to all three of its vertices. This external vertex therefore has 3 in-neighbors in the cycle, contradicting the assumption that every external vertex has at most 2 in-neighbors in the cycle.
The adjacency relation of the digraph is decidable.
For any two vertices u and v, unfolding the definition of the graph reduces adjacency to checking whether the integer value of (v - u) belongs to the set {1, 2, 3, 5, 6, 7, 13}, which Lean's typeclass inference resolves as decidable set membership.
intro u v unfold digraph_safe17_graph infer_instance
The cycle C is represented by a duplicate-free list of vertices connected cyclically.
Unpacking the definition of a directed cycle on C yields a list l without duplicates whose set of elements is C, whose consecutive elements are adjacent, and whose last element is adjacent to its head.
classical obtain ⟨l,hn,hlen0,hset,hchain,hclose⟩ := hcycleThe list l has length 3.
Since l has no duplicates, List.toFinset_card_of_nodup equates its length to the cardinality of its underlying finset, which is C; since |C| = 3, integer arithmetic closes the goal.
uses
List.toFinset_card_of_noduphave hlen : l.length = 3 := by have h := List.toFinset_card_of_nodup hn rw [hset,hcard] at h omega
The list l consists of three vertices u, a, b.
By case analysis on the list l, any length other than 3 contradicts the known length, leaving only the shape l = [u, a, b].
have hshape : ∃ u a b, l = [u,a,b] := 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 => simp at hlen | cons b l => cases l with | nil => exact ⟨u,a,b,rfl⟩ | cons c l => simp at hlen obtain ⟨u,a,b,rfl⟩ := hshape
The vertices u, a, b are pairwise distinct, span C, and form a directed triangle.
Because l = [u, a, b], its vertex set is {u, a, b} = C. The chain condition decomposes via List.isChain_cons_cons into edges u → a and a → b. The cycle closure condition gives b → u using List.head?_cons and Option.some.injEq. Duplicate-freeness of l yields pairwise distinctness of u, a, b with and_assoc.
uses
List.isChain_cons_cons,List.head?_cons,Option.some.injEq,and_assochave hcset : ({u,a,b} : Finset (Fin 17)) = C := by simpa using hset have hchain' : digraph_safe17_graph.Adj u a ∧ digraph_safe17_graph.Adj a b := by simpa [List.isChain_cons_cons] using hchain have hbu : digraph_safe17_graph.Adj b 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 have hdistinct : u ≠ a ∧ u ≠ b ∧ a ≠ b := by simpa [and_assoc] using hn
There exists an external vertex v outside C with directed edges to u, a, and b.
Applying the lemma digraph_safe17_triangle_unsafe to the directed triangle u → a → b → u provides a vertex v distinct from u, a, and b (hence not in C) with edges v → u, v → a, and v → b.
uses
digraph_safe17_triangle_unsafeobtain ⟨v,hvu,hva,hvb,hv0,hv1,hv2⟩ := digraph_safe17_triangle_unsafe u a b hchain'.1 hchain'.2 hbu have hv : v ∉ C := by rw [← hcset]; simp [hvu,hva,hvb]
The existence of three edges from an external vertex contradicts the safety condition, proving False.
The lemma digraph_safe17_three_neighbors_not_safe shows that having an external vertex v ∉ C with directed edges to three distinct vertices u, a, b ∈ C directly contradicts the hypothesis that every external vertex has at most 2 neighbors in C.
uses
digraph_safe17_three_neighbors_not_safeapply digraph_safe17_three_neighbors_not_safe C v u a b hv hdistinct.1 hdistinct.2.1 hdistinct.2.2 · rw [← hcset]; simp · rw [← hcset]; simp · rw [← hcset]; simp · exact hv0 · exact hv1 · exact hv2 · exact hsafe
List.toFinset_card_of_nodup- The cardinality of the finset of elements of a duplicate-free list equals the length of the list.
List.isChain_cons_cons- A list with at least two elements is a chain with respect to a relation R if and only if R holds between the first two elements and the tail is a chain.
List.head?_cons- The optional head of a cons list `a :: l` is `some a`.
Option.some.injEq- `some x = some y` is equivalent to `x = y`.
and_assoc- Conjunction is associative: `(P ∧ Q) ∧ R` is equivalent to `P ∧ Q ∧ R`.
digraph_safe17_triangle_unsafe- For every directed triangle in the graph, there exists a fourth vertex with directed edges to all three triangle vertices.
digraph_safe17_three_neighbors_not_safe- If an external vertex has directed edges to three distinct vertices of a subset C, then C violates the 2-neighbor budget safety condition.
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_final_decAdj_2 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instanceset_option maxHeartbeats 0set_option maxRecDepth 100000theorem digraph_safe17_triangle_cycle_unsafe (C : Finset (Fin 17)) (hcycle : digraph_directed_cycle_on digraph_safe17_graph C) (hcard : C.card = 3) (hsafe : ∀ x ∉ C, (C.filter fun w => digraph_safe17_graph.Adj x w).card ≤ 2) : False := by classical obtain ⟨l,hn,hlen0,hset,hchain,hclose⟩ := hcycle have hlen : l.length = 3 := by have h := List.toFinset_card_of_nodup hn rw [hset,hcard] at h omega have hshape : ∃ u a b, l = [u,a,b] := 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 => simp at hlen | cons b l => cases l with | nil => exact ⟨u,a,b,rfl⟩ | cons c l => simp at hlen obtain ⟨u,a,b,rfl⟩ := hshape have hcset : ({u,a,b} : Finset (Fin 17)) = C := by simpa using hset have hchain' : digraph_safe17_graph.Adj u a ∧ digraph_safe17_graph.Adj a b := by simpa [List.isChain_cons_cons] using hchain have hbu : digraph_safe17_graph.Adj b 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 have hdistinct : u ≠ a ∧ u ≠ b ∧ a ≠ b := by simpa [and_assoc] using hn obtain ⟨v,hvu,hva,hvb,hv0,hv1,hv2⟩ := digraph_safe17_triangle_unsafe u a b hchain'.1 hchain'.2 hbu have hv : v ∉ C := by rw [← hcset]; simp [hvu,hva,hvb] apply digraph_safe17_three_neighbors_not_safe C v u a b hv hdistinct.1 hdistinct.2.1 hdistinct.2.2 · rw [← hcset]; simp · rw [← hcset]; simp · rw [← hcset]; simp · exact hv0 · exact hv1 · exact hv2 · exact hsafe