Definition:Vertex Cut

Definition

Let $G = \struct {V, E}$ be a graph.

A vertex cut of $G$ is a set of vertices $W \subseteq \map V G$ such that the vertex deletion $G \setminus W$ is disconnected.

Examples

Arbitrary Example

Removing $\set {B, C, F}$ would also remove all the dotted edges and leave this graph with two components:

one containing the vertices $A$ and $E$

and

one containing the vertices $D$, $G$, $H$, and $I$.

Thus $\set {B, C, F}$ is a vertex cut.

Also see

• Definition:Vertex Deletion

• Definition:Cut-Vertex: a singleton vertex cut

• Results about vertex cuts can be found here.