digraph_safe17_three_neighbors_not_safe
An outside vertex pointing to three distinct vertices in a set violates the displayed two-neighbor safety condition.
Statement
theorem digraph_safe17_three_neighbors_not_safe (C : Finset (Fin 17)) (v p q r : Fin 17) (hv : v ∉ C) (hpq : p ≠ q) (hpr : p ≠ r) (hqr : q ≠ r) (hp : p ∈ C) (hq : q ∈ C) (hr : r ∈ C) (hvp : digraph_safe17_graph.Adj v p) (hvq : digraph_safe17_graph.Adj v q) (hvr : digraph_safe17_graph.Adj v r) (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 1
- digraph_safe17_graphThe seventeen-vertex cyclic digraph with the displayed seven out-steps.
- 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_triangle_cycle_unsafeNo directed triangle in the displayed graph is safe for deletion with a two-neighbor budget.
The proof, explained
The proof shows by contradiction that a vertex v ∉ C cannot have three distinct neighbors p, q, r in C under the safety condition. Since p, q, r are pairwise distinct elements of C adjacent to v, the set {p, q, r} has cardinality 3 and is a subset of the neighbors of v in C. Hence v has at least 3 neighbors in C, which directly contradicts the safety hypothesis that any vertex outside C has at most 2 neighbors in C.
The adjacency relation of digraph_safe17_graph is decidable. automation
For any vertices u and v, unfolding the definition of digraph_safe17_graph reduces adjacency to checking whether (v - u).val belongs to the explicit finite set {1, 2, 3, 5, 6, 7, 13}, which typeclass inference automatically decides.
intro u v unfold digraph_safe17_graph infer_instance
The three distinct vertices {p, q, r} form a subset of the neighbors of v in C.
Using classical logic, to show {p, q, r} ⊆ {w ∈ C | Adj v w}, take any element x ∈ {p, q, r}. By definition of set insertion and singleton, x must be p, q, or r. In each case, the vertex belongs to C and is adjacent to v by assumption (hp and hvp for p, hq and hvq for q, hr and hvr for r), so by Finset.mem_filter.mpr it satisfies the membership condition of the filtered set.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.mem_filter.mprclassical have hsub : ({p,q,r} : Finset (Fin 17)) ⊆ C.filter fun w => digraph_safe17_graph.Adj v w := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact Finset.mem_filter.mpr ⟨hp,hvp⟩ · exact Finset.mem_filter.mpr ⟨hq,hvq⟩ · exact Finset.mem_filter.mpr ⟨hr,hvr⟩
The set {p, q, r} has cardinality 3. automation
Because p, q, and r are pairwise distinct (hpq : p ≠ q, hpr : p ≠ r, hqr : q ≠ r), simplifying the cardinality of the explicit 3-element set evaluates to 3.
have hcard : ({p,q,r} : Finset (Fin 17)).card = 3 := by simp [hpq,hpr,hqr]
The lower bound of 3 neighbors contradicts the safety condition at v, yielding False. automation
By Finset.card_le_card, the subset inclusion implies that the number of neighbors of v in C is at least |{p, q, r}| = 3. But v ∉ C, so the safety hypothesis hsafe applied to v guarantees that this count is at most 2. Linear arithmetic (omega) derives a contradiction from 3 ≤ card ≤ 2.
uses
Finset.card_le_cardhave hc := Finset.card_le_card hsub have hb := hsafe v hv omega
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
Finset.mem_filter.mpr- If x ∈ s and p x holds, then x belongs to the filtered set {w ∈ s | p w}.
Finset.card_le_card- If s is a subset of t, then the cardinality of s is at most the cardinality of t.
- The private instance on lines 1–4 establishes decidability of the adjacency relation so that the neighborhood filter `C.filter` in the theorem statement is well-typed.
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_1 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instanceset_option maxHeartbeats 0set_option maxRecDepth 100000theorem digraph_safe17_three_neighbors_not_safe (C : Finset (Fin 17)) (v p q r : Fin 17) (hv : v ∉ C) (hpq : p ≠ q) (hpr : p ≠ r) (hqr : q ≠ r) (hp : p ∈ C) (hq : q ∈ C) (hr : r ∈ C) (hvp : digraph_safe17_graph.Adj v p) (hvq : digraph_safe17_graph.Adj v q) (hvr : digraph_safe17_graph.Adj v r) (hsafe : ∀ x ∉ C, (C.filter fun w => digraph_safe17_graph.Adj x w).card ≤ 2) : False := by classical have hsub : ({p,q,r} : Finset (Fin 17)) ⊆ C.filter fun w => digraph_safe17_graph.Adj v w := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact Finset.mem_filter.mpr ⟨hp,hvp⟩ · exact Finset.mem_filter.mpr ⟨hq,hvq⟩ · exact Finset.mem_filter.mpr ⟨hr,hvr⟩ have hcard : ({p,q,r} : Finset (Fin 17)).card = 3 := by simp [hpq,hpr,hqr] have hc := Finset.card_le_card hsub have hb := hsafe v hv omega