The connectivity of a graph does not exceed its minimum degree

Question

Prove that for every graph $G: \mathcal K(G) \le \delta G$

$\mathcal K(G)$ is the connectivity of $G$

$\delta G$ is the minimum degree of $G$

This is a theorem in Graph Theory that I believe needs to be proved through three cases.

1. Connected noncomplete

2. Disconnected

3. Complete

If this is correct?

Answer 1

Fix any undirected graph $G$, and consider any node $v$ achieving its minimum degree $s=\delta(G)$. $v$ has $s$ neighbors $u_1,\dots, u_s$; removing all of them disconnects $G$, as afterwards $v$ is alone in its connected component. Therefore, $s$ is at least the connectivity $\mathcal{K}(G)$, which is the minimum number of nodes to remove in order to disconnect $G$.

If you want to consider your 3 cases, this falls under cases 2 and 3; case 1 is straightforward, as then $\delta(G)=\mathcal{K}(G)=0$.

PS: I assumed you were referring to vertex-connectivity; the proof is the same with edge-connectivity.