AFTD Auto-Formalizing Theoretical Domains

poc8_connb_sound

theoremverified

If the Boolean connectivity test accepts S, then S induces a connected subgraph of G.

Statement

theorem poc8_connb_sound (S : Fin 8 → Bool) (h : poc8_connb S = true) :
    is_connected_vertex_set poc8_graph {x | S x = true}
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 4
  • poc8_connbBoolean connectivity test: some vertex r of S reaches every vertex of S within 7 BFS steps inside S.
  • poc8_close_soundEvery vertex reached by the BFS iteration from r inside S lies in S and is reachable from r in the subgraph induced by S.
  • is_connected_vertex_setA vertex set S of a graph G is connected if the subgraph of G induced by S is connected (in particular S is nonempty).
  • 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_linked_two_threeThe 8-vertex graph G is (2,3)-linked: any 2 terminals and 3 further terminals are separated by a connected bipartition of G.

Lean source view module on GitHub

theorem poc8_connb_sound (S : Fin 8 → Bool) (h : poc8_connb S = true) :    is_connected_vertex_set poc8_graph {x | S x = true} := by  simp only [poc8_connb, List.any_eq_true, List.all_eq_true, List.mem_finRange, true_and,    Bool.and_eq_true, Bool.or_eq_true, Bool.not_eq_true', forall_const] at h  obtain ⟨r, hr, hall⟩ := h  have key : ∀ v : {x | S x = true},      (poc8_graph.induce {x | S x = true}).Reachable ⟨r, hr⟩ v := by    rintro ⟨v, hv⟩    rcases hall v with h | h    · simp only [Set.mem_ofPred_eq] at hv      rw [hv] at h      exact absurd h (by decide)    · exact (poc8_close_sound S r hr 7 v h).2  have : Nonempty {x | S x = true} := ⟨⟨r, hr⟩⟩  exact ⟨fun a b => (key a).symm.trans (key b)⟩
See it in the graphDiscuss this resultChallenge it