AFTD Auto-Formalizing Theoretical Domains

poc8_close_sound

theoremverified

Every vertex reached by the BFS iteration from r inside S lies in S and is reachable from r in the subgraph induced by S.

Statement

theorem poc8_close_sound (S : Fin 8 → Bool) (r : Fin 8) (hr : S r = true) :
    ∀ k v, poc8_close S (fun w => w == r) k v = true →
      ∃ hv : S v = true, (poc8_graph.induce {x | S x = true}).Reachable ⟨r, hr⟩ ⟨v, hv⟩
Source
step towards poc_linkedness_conjecture_counterexample (counterexample to arXiv:1908.05433, Conjecture 3.10; kernel-checked certificate)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • poc8_closek breadth-first-search steps inside S starting from R.
  • poc8_stepOne breadth-first-search step inside S: add to R every vertex of S adjacent to a vertex of R.
  • poc8_graphThe 8-vertex graph G with edges 04, 05, 06, 07, 13, 15, 16, 17, 23, 24, 26, 27, 36, 37, 45, 47, 57, 67.
Used by 1
  • poc8_connb_soundIf the Boolean connectivity test accepts S, then S induces a connected subgraph of G.

Lean source view module on GitHub

theorem poc8_close_sound (S : Fin 8 → Bool) (r : Fin 8) (hr : S r = true) :    ∀ k v, poc8_close S (fun w => w == r) k v = true →      ∃ hv : S v = true, (poc8_graph.induce {x | S x = true}).Reachable ⟨r, hr⟩ ⟨v, hv⟩ := by  intro k  induction k with  | zero =>    intro v hv    simp only [poc8_close, beq_iff_eq] at hv    subst hv    exact ⟨hr, SimpleGraph.Reachable.refl _⟩  | succ k ih =>    intro v hv    simp only [poc8_close, poc8_step, Bool.or_eq_true, Bool.and_eq_true, List.any_eq_true,      List.mem_finRange, true_and] at hv    rcases hv with hv | ⟨hSv, w, hw, hadj⟩    · exact ih v hv    · obtain ⟨hSw, hreach⟩ := ih w hw      have hA : (poc8_graph.induce {x | S x = true}).Adj ⟨w, hSw⟩ ⟨v, hSv⟩ := hadj      exact ⟨hSv, hreach.trans hA.reachable⟩
See it in the graphDiscuss this resultChallenge it