= Solution
{c}
A <graph> is a <k-connected graph> if it has at least $k+1$ <vertices> and deleting any <set> of fewer than $k$ <vertices>, together with their incident <edges>, leaves a <connected graph>.
The <vertex connectivity> $\kappa(G)$ is the largest such $k$. Equivalently, for a <graph> with at least two <vertices>, it is the smallest number of <vertices> whose deletion either disconnects the <graph> or leaves a single <vertex>. The latter convention gives $\kappa(K_n)=n-1$ for a <complete graph>. A disconnected <graph> has <vertex connectivity> zero; one usually also sets $\kappa(K_1)=0$.
For distinct nonadjacent <vertices> $x,y$, the <local connectivity> is
$$
\boxed{\kappa_G(x,y)=\min\{|S|:S\subseteq V(G)\setminus\{x,y\},\ \text{there is no }x\text{--}y\text{ path in }G-S\}.}
$$
Such a <set> $S$ is an $x$–$y$ <vertex separator>. By <Menger's theorem>, <local connectivity> also equals the maximum number of <internally vertex-disjoint paths> from $x$ to $y$. If no <graph path> exists already, the empty <vertex separator> gives zero.
Back to article page
