Cut Vertices and Cut Edges
What You'll Learn
You'll learn to identify cut vertices and cut edges—the critical points and links whose removal disconnects a graph—and understand why they matter for graph robustness.
Core Idea
Imagine a social network or transportation system. Some people or roads are crucial: remove them, and the whole network falls apart into isolated groups. In graph theory, these vulnerabilities have precise names.
A cut vertex (or articulation point) is a vertex whose removal increases the number of connected components in the graph. In other words, deleting that single vertex—and all edges incident to it—breaks the graph into two or more disconnected pieces.
A cut edge (or bridge) is an edge whose removal increases the number of connected components. Unlike a cut vertex, you're only removing one edge, not an entire vertex and its neighborhood.
Why They Matter
Connectivity and vulnerability: Cut vertices and cut edges reveal structural weaknesses. A graph with many cut vertices is fragile; removing just one node can partition the network. Graphs without cut vertices (called biconnected graphs) are more robust—any single vertex can fail without breaking connectivity.
Real-world analogies:
- Transportation: A bridge (cut edge) connects two landmasses; destroying it isolates them.
- Communication: A central server (cut vertex) whose failure splits a network into isolated clusters.
- Social networks: An influencer who is the only link between two friend groups.
Finding Them
Visually, look for "bottleneck" vertices or edges. Algorithmically, depth-first search (DFS) can identify them efficiently, though the mechanics involve concepts like discovery times and low-link values (beyond our current scope).
Key Takeaway:
Cut vertices and cut edges are single points of failure in a graph—removing them disconnects the structure, revealing critical dependencies and guiding efforts to strengthen network resilience.