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