Connectivity and Cut Vertices

Understanding when a graph can be disconnected by removing vertices or edges is central to network reliability and structural analysis. We prove key results about connectivity and characterize graphs without cut vertices.

TheoremEquivalent Characterizations of 2-Connectivity

For a graph $G$ with at least 3 vertices, the following are equivalent:

$G$ is 2-connected
$G$ has no cut vertices
Every pair of vertices lies on a common cycle
For any vertex $v$ and any edge $e$ , there exists a path from one endpoint of $e$ to the other that passes through $v$

Proof

(1) $\Rightarrow$ (2): If $v$ is a cut vertex, removing $v$ disconnects $G$ , contradicting 2-connectivity.

(2) $\Rightarrow$ (3): Let $u, v$ be distinct vertices. Since $G$ has no cut vertices, $G - u$ is connected, so there exists a path $P$ from $v$ to any neighbor $w$ of $u$ not using $u$ . Similarly, $G - v$ is connected, giving a path $Q$ from $u$ to $w$ not using $v$ . Combining these paths creates a cycle through $u$ and $v$ .

(3) $\Rightarrow$ (4): Let $e = \{x,y\}$ and $v$ be given. By (3), $x$ and $y$ lie on a cycle $C$ . If $v \in C$ , we use the portion of $C$ from $x$ to $y$ through $v$ . If $v \notin C$ , we again use (3) to find a cycle through $v$ and $x$ , then route from $x$ through $v$ to reach $y$ via paths avoiding the edge $e$ .

(4) $\Rightarrow$ (1): Suppose $G$ is not 2-connected. Then $\kappa(G) = 1$ , so there exists a cut vertex $w$ . Let $u$ and $v$ be vertices in different components of $G - w$ . But then (4) implies we can connect $u$ to $v$ via a path through $w$ that avoids some edge $e = \{w, u\}$ , contradicting that $w$ separates $u$ and $v$ .

■

TheoremWhitney's Theorem on Connectivity

For any graph $G$ , we have: $\kappa(G) \leq \lambda(G) \leq \delta(G)$ where $\kappa(G)$ is vertex connectivity, $\lambda(G)$ is edge connectivity, and $\delta(G)$ is minimum degree.

Proof

Second inequality: Let $v$ be a vertex with $\deg(v) = \delta(G)$ . Removing all $\delta(G)$ edges incident to $v$ disconnects $G$ (isolating $v$ ), so $\lambda(G) \leq \delta(G)$ .

First inequality: Let $S$ be a minimum edge cut with $|S| = \lambda(G)$ , separating $G$ into components $A$ and $B$ . If there exists a vertex $w$ incident to all edges in $S$ , then $w$ is a cut vertex and $\kappa(G) = 1 \leq \lambda(G)$ .

Otherwise, construct a vertex cut as follows: for each edge in $S$ from $A$ to $B$ , include its endpoint in $A$ if it has other neighbors in $A$ , or its endpoint in $B$ otherwise. This creates a vertex cut of size at most $|S|$ , giving $\kappa(G) \leq \lambda(G)$ .

■

ExampleStrict Inequalities

For the complete bipartite graph $K_{2,3}$ , we have $\delta(K_{2,3}) = 2$ (the degree of vertices in the smaller part), $\lambda(K_{2,3}) = 2$ (removing two edges disconnects it), and $\kappa(K_{2,3}) = 2$ (removing two vertices can disconnect). Here equality holds throughout.

However, for a "bow-tie" graph (two triangles sharing a single vertex), $\kappa(G) = 1 < \lambda(G) = 2 < \delta(G) = 2$ (for non-central vertices), showing all inequalities can be strict.

Remark

Menger's theorem provides a deeper connection: the minimum size of a vertex cut separating $u$ and $v$ equals the maximum number of vertex-disjoint paths between them. This max-flow min-cut duality underlies many connectivity results and algorithms.