11.3 Graph connectivity and cut vertices

Connected vs Disconnected Graphs

Graph Connectivity Fundamentals

A graph is connected if there's a path between every pair of vertices. If even one pair of vertices has no path between them, the graph is disconnected. This distinction matters because most useful properties of graphs (spanning trees, unique shortest paths, etc.) depend on connectivity.

A disconnected graph breaks into connected components, which are maximal connected subgraphs. "Maximal" here means you can't add another vertex from the graph and keep the subgraph connected.

Beyond the binary connected/disconnected question, we can measure how connected a graph is:

• Vertex connectivity $\kappa(G)$: the minimum number of vertices whose removal disconnects the graph (or reduces it to a single vertex)
• Edge connectivity $\lambda(G)$: the minimum number of edges whose removal disconnects the graph
• A graph is k-connected if $\kappa(G) \geq k$, meaning it stays connected after removing any $k - 1$ vertices

Menger's theorem ties this together: the maximum number of vertex-disjoint paths between two nonadjacent vertices $u$ and $v$ equals the minimum number of vertices whose removal separates $u$ from $v$. This gives connectivity a concrete interpretation in terms of independent paths.

Properties of Connected and Disconnected Graphs

• Every connected graph has at least $n - 1$ edges, where $n$ is the number of vertices. A connected graph with exactly $n - 1$ edges is a tree.
• Every connected graph contains a spanning tree (a subgraph that's a tree touching all vertices).
• A disconnected graph has $\kappa(G) = 0$ by definition.
• Complete graphs $K_n$ are examples of highly connected graphs: $\kappa(K_n) = n - 1$.
• Forests (disjoint unions of trees) are classic examples of disconnected graphs when they contain more than one tree.

Identifying Cut Vertices and Bridges

Definitions and Significance

A cut vertex (also called an articulation point) is a vertex whose removal increases the number of connected components. Similarly, a bridge (or cut edge) is an edge whose removal increases the number of connected components.

Think of a cut vertex as a single point of failure. If your network has one router that connects two halves of the system, that router is a cut vertex. Remove it, and the two halves can't communicate.

A graph with no cut vertices (other than trivially having fewer than 3 vertices) is called biconnected. Biconnected graphs are more resilient because no single vertex removal can disconnect them. Every biconnected graph has at least two vertex-disjoint paths between any pair of vertices.

Any graph can be decomposed into its biconnected components (also called blocks), which overlap only at cut vertices. This block-cut tree structure gives you a clean picture of where the graph's vulnerabilities lie.

Detection Methods

The standard approach for finding cut vertices uses depth-first search (DFS). Here's how it works:

1. Run a DFS from any vertex, recording the discovery time $d[v]$ for each vertex $v$.

2. For each vertex, compute $low[v]$, defined as the minimum of:

   • $d[v]$ itself
   • $d[w]$ for any back edge from $v$ (or a descendant of $v$) to an ancestor $w$

3. A non-root vertex $u$ is a cut vertex if it has a child $v$ in the DFS tree such that $low[v] \geq d[u]$. This means no descendant of $v$ can "reach back" above $u$, so removing $u$ traps $v$'s subtree.

4. The root of the DFS tree is a cut vertex if and only if it has two or more children in the DFS tree.

Bridge detection works almost identically: an edge $(u, v)$ where $v$ is a child of $u$ in the DFS tree is a bridge if $low[v] > d[u]$ (strict inequality, since the edge itself can't be used to reach back).

Tarjan's algorithm implements exactly this procedure and runs in $O(V + E)$ time, making it efficient even for large graphs.

Impact of Removing Cut Vertices or Bridges

Effects on Graph Structure

• Removing a bridge always splits its component into exactly two components (the two sides of the bridge).
• Removing a cut vertex can split its component into two or more components, depending on how many separate "branches" depended on that vertex.
• The number of components a cut vertex $v$ creates upon removal equals the number of biconnected components that contain $v$.

Whitney's inequality relates the two connectivity measures to minimum degree:

$\kappa(G) \leq \lambda(G) \leq \delta(G)$

where $\delta(G)$ is the minimum degree of any vertex in $G$. This tells you that vertex connectivity is always the tightest bottleneck.

Applications in Network Analysis

Cut vertices and bridges show up whenever you need to assess how robust a network is:

• In computer networks, a bridge between two subnetworks means a single link failure partitions the network. Redundant links eliminate bridges.
• In transportation networks, a cut vertex might be a city whose airport connects two otherwise separate regions.
• Network reliability analysis often starts by identifying all cut vertices and bridges, then asking: what's the cost of adding redundancy to eliminate them?

Quantifying the impact of removal goes beyond just counting components. You might also track how the diameter (longest shortest path) changes, or how average path length increases, to understand degraded-but-still-connected performance.

Connectivity Algorithms and Cut Vertices

Fundamental Algorithms

• DFS is the workhorse for connectivity problems. A single DFS determines whether a graph is connected, and with the $low$ value extension, it finds all cut vertices and bridges.
• BFS can verify connectivity by checking whether all vertices are reachable from a starting vertex. If the BFS tree includes all $n$ vertices, the graph is connected.
• The max-flow min-cut theorem connects to connectivity at a deeper level: the minimum number of edges (or vertices) you must remove to separate two specific vertices equals the maximum flow between them. The Ford-Fulkerson algorithm computes this.

Algorithm Implementation

For Tarjan's cut vertex algorithm, here are the key implementation details:

1. Maintain a global timer that increments with each new vertex discovery.
2. Store $d[v]$ and $low[v]$ arrays indexed by vertex.
3. During DFS, when you visit a child $v$ from $u$, after the recursive call returns, update $low[u] = \min(low[u], low[v])$.
4. When you encounter a back edge to an already-visited ancestor $w$, update $low[u] = \min(low[u], d[w])$.
5. After processing all neighbors of $u$, check the cut vertex conditions (root with 2+ children, or non-root with a child satisfying $low[v] \geq d[u]$).

The time complexity is $O(V + E)$ since each vertex and edge is processed exactly once during DFS. For very large graphs, disjoint-set (union-find) data structures with path compression and union by rank can speed up dynamic connectivity queries, supporting near-constant-time operations per query.