Past exam of the graph theory course of the University of Oxford / 2023 / 3 / a

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 isSuch 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.