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