K-Connectivity Implies Lesser Connectivity
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$