Vertex cuts, edge cuts, vertex connectivity $\kappa (G)$ and edge connectivity $\lambda (G)$, with conventions for complete and one-vertex graphs

Let $G=(V,E)$ be connected with $n=\mathrm{\mid }V\mathrm{\mid }\ge 2$. A vertex cut is a set $S\subseteq V$ for which $G-S$ is disconnected or has at most one vertex. An edge cut is a set $F\subseteq E$ for which $G-F$ is disconnected. The vertex connectivity and edge connectivity are

$\kappa (G):=\min \{\mathrm{\mid }S\mathrm{\mid }:S\text{ is a vertex cut}\},\lambda (G):=\min \{\mathrm{\mid }F\mathrm{\mid }:F\text{ is an edge cut}\}\mathrm{.}$

The finite families being minimized are nonempty: deleting all but one vertex is a vertex cut, and deleting all edges is an edge cut. For the complete graph $K_n$, no deletion leaving at least two vertices disconnects it, so the first definition gives the standard exceptional convention $\kappa (K_n)=n-1$.

For the one-vertex graph $K_1$, set $\kappa (K_1)=\lambda (K_1)=0$. The null graph and every disconnected graph are outside the domain of these two connectivity parameters under this convention. Thus the inequalities involving $\delta (G)$ are stated only for nontrivial connected graphs, where the vertex set is nonempty and $\delta (G)$ is defined.