AFTD Auto-Formalizing Theoretical Domains

digraph_safe17_three_neighbors_not_safe

theoremverified

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
Used by 2

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.

  1. 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.

    lines 2–4

      intro u v
      unfold digraph_safe17_graph
      infer_instance
  2. 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.

    lines 16–23

    uses Finset.mem_insert, Finset.mem_singleton, Finset.mem_filter.mpr

      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⟩
  3. 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.

    line 24

      have hcard : ({p,q,r} : Finset (Fin 17)).card = 3 := by simp [hpq,hpr,hqr]
  4. 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.

    lines 25–27

    uses Finset.card_le_card

      have 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.

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

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
See it in the graphDiscuss this resultChallenge it