Minimum Degree is at Least Connectivity

This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

Theorem

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

Then:

$\map \delta G \ge \map \kappa G$

That is, the minimum degree of $G$ is at least its connectivity.

Proof

Pick a vertex $v \in G$ with $\map {\deg_G} v = \map \delta G$, that is, a vertex with minimum degree.

Recall that $\map {\Gamma_G} v$ is the neighborhood of $v$ in $G$.

Suppose that $V = \map {\Gamma_G} v \cup \set v$.

That is, that $v$ is adjacent to all other vertices of $G$.

Then:

$\card V = \card {\map {\Gamma_G} v} + 1 = \map \delta G + 1$

By definition, $\map \kappa G < \card V$, so $\map \kappa G \le \map \delta G$.

Otherwise, there is at least one vertex of $G$ not adjacent to $v$.

So, deleting $\map {\Gamma_G} v$ from $G$ leaves $v$ isolated.

Thus $\map {\Gamma_G} v$ is a vertex cut of size $\map \delta G$.

Since $G$ has a vertex cut of size $\map \delta G$, it follows that $\map \kappa G \le \map \delta G$.

$\blacksquare$

Notes

This bound is not necessarily tight:

In this example, the minimum degree of the graph is $2$, yet $C$ is a cut-vertex and so this graph has connectivity $1$.