AFTD Auto-Formalizing Theoretical Domains

is_connected_vertex_set

def

A vertex set S of a graph G is connected if the subgraph of G induced by S is connected (in particular S is nonempty).

Statement

def is_connected_vertex_set {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop
Defined in
arXiv:1908.05433, Sec. 2 (connected bundles: vertex sets inducing a connected subgraph)
Verified
06 Oct 2026
Axioms
none listed
Used by 9
  • poc8_cutb_soundIf the Boolean cut test accepts (S, R), then S does not induce a connected subgraph of G.
  • 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…
  • poc8_connb_soundIf the Boolean connectivity test accepts S, then S induces a connected subgraph of G.
  • op_599_complete_graph_equalityFor the complete graph on at least 1 vertex and any real lambda >= 1, the lambda-weighted mean order of a nonempty connected induced…
  • 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_discb_soundIf the Boolean disconnectedness test accepts S, then S does not induce a connected subgraph of G.
  • conn_set_polyThe connected-set generating polynomial Z_G = sum over nonempty vertex sets S inducing a connected subgraph of X^{|S|}.
  • is_ab_linkedA graph G is (a,b)-linked if for any disjoint vertex sets M1, M2 with |M1| = a and |M2| = b there are disjoint vertex sets S1 ⊇ M1 and S2…
  • connected_induced_mean_orderThe lambda-weighted mean order of a nonempty connected induced vertex set in a graph G is lambda * Z'_G(lambda) / Z_G(lambda), where…

Lean source view module on GitHub

/-- `S` induces a connected subgraph of `G` (connectedness includes nonemptiness). -/
def is_connected_vertex_set {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop :=
  (G.induce S).Connected
See it in the graphDiscuss this resultChallenge it