AFTD Auto-Formalizing Theoretical Domains

poc8_not_connected_of_cut

theoremverified

Cut 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 induce a connected subgraph.

Statement

theorem poc8_not_connected_of_cut {V : Type*} (G : SimpleGraph V) (S R : Set V) (a b : V)
    (ha : a ∈ S) (haR : a ∈ R) (hb : b ∈ S) (hbR : b ∉ R)
    (hcl : ∀ v w, v ∈ S → w ∈ R → G.Adj w v → v ∈ R) :
    ¬ is_connected_vertex_set G S
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 1
  • 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).
Used by 2
  • poc8_cutb_soundIf the Boolean cut test accepts (S, R), then S does not induce a connected subgraph of G.
  • poc8_not_linked_two_fourG is not (2,4)-linked: for M1 = {0,1} and M2 = {2,5,6,7}, any S1 ⊇ M1 disjoint from S2 ⊇ M2 lies in {0,1,3,4}, and {0,4} is cut off from…

Lean source view module on GitHub

theorem poc8_not_connected_of_cut {V : Type*} (G : SimpleGraph V) (S R : Set V) (a b : V)    (ha : a ∈ S) (haR : a ∈ R) (hb : b ∈ S) (hbR : b ∉ R)    (hcl : ∀ v w, v ∈ S → w ∈ R → G.Adj w v → v ∈ R) :    ¬ is_connected_vertex_set G S := by  intro hc  obtain ⟨p⟩ := hc.preconnected ⟨a, ha⟩ ⟨b, hb⟩  have key : ∀ (x y : S) (q : (G.induce S).Walk x y), (x : V) ∈ R → (y : V) ∈ R := by    intro x y q    induction q with    | nil => exact id    | cons h q ih => intro hx; exact ih (hcl _ _ (Subtype.prop _) hx h)  exact hbR (key _ _ p haR)
See it in the graphDiscuss this resultChallenge it