poc8_discb_sound
theoremverified
If the Boolean disconnectedness test accepts S, then S does not induce a connected subgraph of G.
Statement
theorem poc8_discb_sound (S : Fin 8 → Bool) (h : poc8_discb 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
Quot.soundpropext- Built on 4
- poc8_discbBoolean disconnectedness test: S is empty, or the BFS closure inside S of some vertex of S is a proper cut of S.
- poc8_cutb_soundIf the Boolean cut test accepts (S, R), then S does not induce a connected subgraph of G.
- 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
- poc_linkedness_conjecture_counterexampleCounterexample to arXiv:1908.05433 Conjecture 3.10 for two agents: there is a graph G on 8 vertices that is (2,3)-linked but not…
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_discb_sound (S : Fin 8 → Bool) (h : poc8_discb S = true) : ¬ is_connected_vertex_set poc8_graph {x | S x = true} := by simp only [poc8_discb, Bool.or_eq_true, List.all_eq_true, List.any_eq_true, List.mem_finRange, true_and, Bool.and_eq_true, Bool.not_eq_true', forall_const] at h rcases h with h | ⟨r, _, hcut⟩ · intro hc obtain ⟨⟨v, hv⟩⟩ := hc.nonempty simp only [Set.mem_ofPred_eq] at hv rw [h v] at hv exact absurd hv (by decide) · exact poc8_cutb_sound S _ hcut