K-Connectivity Implies Lesser Connectivity

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $G = \struct {V, E}$ be a $k$-connected graph.

Then $G$ is $l$-connected for all $l \in \Z : 0 < l < k$.


Proof

Suppose that $G$ is $k$-connected.

Then:

$\card V > k > l$
$G$ is connected
If $W$ is a vertex cut of $G$, then $\card W \ge k > l$ so $\card W \ge l$.

$\blacksquare$