AFTD Auto-Formalizing Theoretical Domains

poc8_cutb_sound

theoremverified

If the Boolean cut test accepts (S, R), then S does not induce a connected subgraph of G.

Statement

theorem poc8_cutb_sound (S R : Fin 8 → Bool) (h : poc8_cutb S R = 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 5
  • poc8_cutbBoolean cut test: R is nonempty, R ⊆ S, S ⊄ R, and no edge leads from R to a vertex of S outside R.
  • poc8_not_connected_of_cutCut criterion: if R contains a vertex a of S but misses a vertex b of S, and no edge of G leads from R into S outside R, then S does not…
  • 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.
  • 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_adjAdjacency of the 8-vertex graph with the 18 edges 04, 05, 06, 07, 13, 15, 16, 17, 23, 24, 26, 27, 36, 37, 45, 47, 57, 67, stored as…
Used by 1
  • poc8_discb_soundIf the Boolean disconnectedness test accepts S, then S does not induce a connected subgraph of G.

Lean source view module on GitHub

theorem poc8_cutb_sound (S R : Fin 8 → Bool) (h : poc8_cutb S R = true) :    ¬ is_connected_vertex_set poc8_graph {x | S x = true} := by  simp only [poc8_cutb, 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 ⟨⟨⟨⟨a, ha⟩, hRS⟩, ⟨b, hbS, hbR⟩⟩, hcl⟩ := h  refine poc8_not_connected_of_cut poc8_graph {x | S x = true} {x | R x = true} a b ?_ ha hbS    (by simp [hbR]) ?_  · rcases hRS a with h | h    · rw [ha] at h; exact absurd h (by decide)    · exact h  · intro v w hv hw hadj    simp only [Set.mem_ofPred_eq] at hv hw ⊢    have hadj' : poc8_adj w v = true := hadj    rcases hcl v w with ((h | h) | h) | h    · rw [hv] at h; exact absurd h (by decide)    · rw [hw] at h; exact absurd h (by decide)    · rw [hadj'] at h; exact absurd h (by decide)    · exact h
See it in the graphDiscuss this resultChallenge it