Introduction
A graph does not have to be one piece. It can shatter into isolated islands with no roads between them, or it can be so tightly knit that you need to destroy multiple vertices before it falls apart.
Connectivity is the branch of graph theory that studies this structural property: how well-linked is a graph, and how much damage can it absorb before it breaks apart?
In this post we build the complete connectivity picture — from the simplest idea of “can vertex A reach vertex B?” all the way to the formal vertex connectivity number that measures a graph’s resilience.
Connected and Disconnected Graphs
Definition
A graph is connected if there exists a walk (and therefore a path) between every pair of distinct vertices. If even one pair of vertices has no path between them, the graph is disconnected.
Formally:
A Connected Graph
Every vertex in this graph can reach every other vertex by following edges. Remove any single vertex — the rest stays connected. This graph is connected and has exactly one component.
A Disconnected Graph
This graph immediately falls into three separate islands — no edge crosses between them. Start at A: you can reach B and C, but never D, E, F, or G. This graph is disconnected.
Connected Components
Definition
When a graph is disconnected, it breaks into separate pieces called connected components (or simply components).
A connected component is a maximal connected subgraph — meaning:
- Connected: every vertex inside the component can reach every other vertex inside it
- Maximal: you cannot add any more vertices from the original graph without breaking connectivity — the component is already as large as it can be
The Two Rules of a Component
Every component must satisfy both of these simultaneously:
| Rule | Description |
|---|---|
| Insider Rule | There is a path between any two vertices inside the component |
| Outsider Rule | There is no path from any vertex inside the component to any vertex outside it |
Worked Example
The graph above has three components:
| Component | Vertices | Why it’s maximal |
|---|---|---|
| 1 | A, B, C form a triangle — all connected. No edge leads to D, E, F, or G. | |
| 2 | D, E, F form a triangle — all connected. No edge leads to A, B, C, or G. | |
| 3 | G has no edges at all. It cannot reach anyone. |
Key observations:
- A fully connected graph has exactly 1 component
- The number of components satisfies
- only when the graph has no edges at all (every vertex is isolated)
Isolated Vertices
Definition
An isolated vertex is a vertex with degree 0 — no edges attached to it.
Vertex G in the graph above is isolated. Does it count as a component? Let’s test both rules:
- Insider Rule: Is every vertex in connected to every other? There is only one vertex, so trivially yes.
- Outsider Rule: Can any outside vertex reach G? G has no edges, so no.
✅ G passes both rules. An isolated vertex is a valid, independent connected component of size 1.
Implication: A graph with vertices and no edges has exactly components — one per isolated vertex.
Cut Vertices (Articulation Points)
Definition
A cut vertex (also called an articulation point) is a vertex whose removal increases the number of connected components.
In other words: if you delete the vertex and all its edges, the graph splits into more pieces than before.
Vertex B (red) is the cut vertex here. Remove it and the graph fractures into:
- Left fragment:
- Right fragment:
Without B, no path exists from the left to the right. B was the sole bridge between the two clusters.
Why Cut Vertices Matter
Cut vertices are structural vulnerabilities. Any system modelled as a graph — a computer network, a power grid, a supply chain — that contains a cut vertex has a single point of failure: destroying that one node disconnects the system.
Identifying cut vertices is a classic algorithm problem solved efficiently by DFS in time (Tarjan’s algorithm).
When Does a Cut Vertex Exist?
A connected graph with no cut vertices is called 2-connected (or biconnected). Any two vertices in a 2-connected graph have at least two internally vertex-disjoint paths between them — so losing any single vertex cannot disconnect the graph.
No matter which single vertex you remove from this graph, the remaining five vertices stay connected. This 2-connected graph has no cut vertices and no single point of failure.
Bridges (Cut Edges)
Definition
A bridge (also called a cut edge or isthmus) is an edge whose removal increases the number of connected components.
Edge B–C (red) is the bridge here. It is the only connection between the left cluster and the right cluster . Remove it and the graph splits into two disconnected components.
Bridge vs. Cut Vertex
| Property | Cut Vertex | Bridge |
|---|---|---|
| What is removed | A vertex (and all its edges) | A single edge |
| Effect | Increases | Increases |
| Also called | Articulation point | Cut edge / isthmus |
| Detection algorithm | Tarjan’s DFS — | Tarjan’s DFS — |
Key Relationship
If an edge is a bridge, then at least one of or is a cut vertex — unless both and have degree 1 (leaf nodes, where removing the edge isolates a single vertex).
Bottleneck Property of Cuts
A Bridge Always Splits Into Exactly Two Components
When a bridge is removed from a connected graph, the result always has exactly two components — never more.
Edge B–C (dashed red) is the bridge. The blue cluster and the teal cluster become disconnected the moment B–C is removed. You cannot get more than two components from a single edge removal because one edge can only sever one connection — the graph was one piece before, and it splits into the two sides of that severed edge.
Formal statement: If is connected and is a bridge, then has exactly 2 connected components.
Why not 3 or more? Removing one edge can increase the component count by at most 1. Starting from 1 component, the maximum after removing one edge is .
Cut Vertices as Bottlenecks
A cut vertex is a structural bottleneck — all traffic between the two sides of the graph must pass through it. This has direct engineering consequences:
- Network design: any router or switch that is a cut vertex is a single point of failure. Losing it cuts off part of the network with no alternate route.
- Evacuation planning: a bridge over a river that is the only land crossing is a bridge in both the civil-engineering and the graph-theory sense.
- Supply chains: a single supplier with no alternative who feeds a critical step is a cut vertex in the supply graph.
How Many Components Can a Cut Vertex Create?
Unlike a bridge (which always yields exactly 2 components), a cut vertex can create more than 2 components. Its degree determines how many “branches” it holds together:
| Cut vertex degree | Maximum new components after removal |
|---|---|
| 2 | 2 |
| 3 | 3 |
Removing the cut vertex severs every branch it was holding, each of which becomes its own component (provided those branches are not connected to each other by any other path).
Vertex Connectivity
Definition
The vertex connectivity (kappa) of a connected graph is the minimum number of vertices whose removal either disconnects the graph or reduces it to a single vertex ().
This number measures how robust the graph is against vertex failures.
Interpretation
| Meaning | |
|---|---|
| Graph is already disconnected | |
| Has a cut vertex — one removal suffices to disconnect | |
| 2-connected — need to remove 2 vertices to disconnect | |
| -connected — need to remove vertices to disconnect | |
| Complete graph — maximally connected |
Examples
- The three-component graph above: (already disconnected)
- The cut-vertex graph: (removing B disconnects it)
- The 2-connected hexagon:
- : (must remove all but one vertex)
Edge Connectivity
The analogous measure for edges is the edge connectivity : the minimum number of edges whose removal disconnects .
Whitney’s inequality relates the three measures:
where is the minimum degree of any vertex. Vertex connectivity is always the toughest constraint.
Directed Graph Connectivity
For directed graphs (digraphs), connectivity splits into two distinct concepts.
Strongly Connected
A directed graph is strongly connected if every vertex can reach every other vertex following the direction of edges.
The orange vertices form a directed cycle , guaranteeing mutual reachability. Vertex E (blue) can reach A (via ) and is reachable from B and C. Every vertex can reach every other — this digraph is strongly connected.
Weakly Connected
A directed graph is weakly connected if the underlying undirected graph (ignoring edge directions) is connected. Weakly connected strongly connected: every strongly connected digraph is weakly connected, but not vice versa.
Example of weakly but not strongly connected: A graph (a directed path). Underlying graph is connected (weakly connected), but C cannot reach A — not strongly connected.
Strongly Connected Components (SCCs)
In a digraph, a strongly connected component is a maximal set of vertices that are all mutually reachable. Every digraph decomposes uniquely into SCCs. The condensation graph (contracting each SCC to a single node) is always a DAG (directed acyclic graph).
SCCs are found in using Kosaraju’s algorithm or Tarjan’s SCC algorithm — essential tools in compilers, web crawlers, and deadlock detection.
Summary Table
| Concept | Definition | Symbol |
|---|---|---|
| Connected graph | Path exists between every pair of vertices | — |
| Connected component | Maximal connected subgraph | |
| Isolated vertex | Vertex of degree 0; forms its own component | — |
| Cut vertex | Vertex whose removal increases | — |
| Bridge | Edge whose removal increases | — |
| -connected | Need vertex removals to disconnect | |
| Strongly connected | Mutual reachability in directed graphs | — |
| Weakly connected | Connected when edge directions are ignored | — |
Practice Problems
Problem 1: Counting Components
Question: A graph has 8 vertices and the following edges: {1–2, 2–3, 4–5, 5–6, 6–4}. How many connected components does it have, and which vertices are in each?
Click to reveal solution
Trace reachability from each vertex:
- Start at 1: reach 2 (via 1–2), reach 3 (via 2–3). Component: {1, 2, 3}
- Start at 4: reach 5 (4–5), reach 6 (5–6 or 6–4). Component: {4, 5, 6}
- Vertices 7 and 8 have no edges. Components: {7} and {8}
Answer: 4 components — {1,2,3}, {4,5,6}, {7}, {8}
Problem 2: Is This a Cut Vertex?
Question: In a cycle (pentagon), is any vertex a cut vertex?
Click to reveal solution
Remove any single vertex from $C_5$. The remaining 4 vertices form a path $P_4$ — still connected.
No vertex in $C_n$ (for $n \geq 3$) is a cut vertex. Cycles are 2-connected: $\kappa(C_n) = 2$. You need to remove 2 vertices to disconnect a cycle.
Problem 3: Finding a Bridge
Question: Graph has edges {A–B, B–C, C–D, D–B, A–E}. Which edges are bridges?
Click to reveal solution
Check each edge — is it the only path between its endpoints?
- A–B: Removing it — is there another path from A to B? A can only reach B via A–B or A–E–?. E has no other edges. So A becomes isolated from B,C,D,E. Bridge ✓
- B–C: Removing it — path B→D→C still exists. Not a bridge
- C–D: Removing it — path C→B→D still exists. Not a bridge
- D–B: Removing it — path D→C→B still exists. Not a bridge
- A–E: Removing it — E has no other edges; E becomes isolated. Bridge ✓
Answer: A–B and A–E are bridges. The triangle B–C–D has no bridges.
Problem 4: Vertex Connectivity
Question: What is ?
Click to reveal solution
In $K_5$ every vertex is adjacent to every other. To disconnect it (or reduce to $K_1$), you need to remove enough vertices to leave at most 1.
$|V| = 5$, so remove 4 vertices → 1 vertex remains (trivially connected).
Removing any 3 vertices leaves 2 vertices which are still connected (they were adjacent in $K_5$).
$\kappa(K_5) = 5 - 1 = 4$. In general, $\kappa(K_n) = n - 1$.
Problem 5: Strongly vs. Weakly Connected
Question: Directed graph has edges , , , . Is it strongly connected?
Click to reveal solution
Check if every vertex can reach every other:
- From A: A→B→C→A ✓, A→B→D ✓
- From B: B→C→A ✓, B→D ✓
- From C: C→A→B ✓, C→A→B→D ✓
- From D: D→? D has no outgoing edges. D cannot reach A, B, or C.
Not strongly connected.
SCCs: {A, B, C} form one SCC (mutually reachable via the cycle). {D} is its own SCC (no outgoing edges to rejoin the cycle).
The underlying undirected graph is connected, so H is weakly connected.
Real-World Applications
Social Networks
Connected components map directly to isolated friend groups. A single component means everyone is reachable (the “six degrees of separation” claim). Multiple components mean the network is fragmented — typical in early-stage networks or after account bans.
Epidemiology
If a contagious disease spreads along edges of a contact network, it can only infect vertices within the same component as the index case. Quarantine in real life is exactly the act of removing vertices (isolating people) to increase the number of components and trap the disease in one of them.
Power Grids and Infrastructure
Cut vertices and bridges are single points of failure. Power engineers explicitly compute and for the grid topology. High-value grids are designed to be at least 2-connected — so that no single substation failure causes a blackout.
Computer Networks
Internet routing protocols (like OSPF) continuously track connectivity. When a router goes down, the routing algorithm must find new paths — it is essentially re-computing components. The internet’s core backbone is designed to be highly connected () precisely to survive node and link failures.
Compilers and Program Analysis
Strongly connected components in a call graph identify recursive clusters of functions. In data-flow analysis, the condensation DAG of the SCC decomposition drives the order in which code blocks are analysed.
Key Takeaways
- A graph is connected if a path exists between every pair of vertices; otherwise it is disconnected.
- Connected components are the maximal connected subgraphs. A connected graph has exactly one component.
- An isolated vertex (degree 0) forms its own component — it satisfies both component rules trivially.
- A cut vertex (articulation point) is a vertex whose removal increases the number of components; it is a structural bottleneck — all paths between the two sides must pass through it.
- A bridge (cut edge) is an edge whose removal increases the number of components. Removing a bridge from a connected graph always creates exactly 2 components.
- Vertex connectivity is the minimum vertex deletions needed to disconnect ; .
- Whitney’s inequality: .
- Directed graphs distinguish strongly connected (mutual reachability along directed edges) from weakly connected (connected when directions are ignored).
- Every directed graph decomposes uniquely into strongly connected components (SCCs).
Explore Further
Use the GraphArena Playground to experiment:
- Build the three-component graph and confirm no walk crosses between components
- Add a single edge connecting two components — watch the component count drop
- Build a graph with a cut vertex, then add one extra edge to eliminate it
- Construct a 2-connected graph and verify no single vertex removal disconnects it
- Build a directed graph and trace which vertices are mutually reachable (SCC detection by hand)
Connectivity is the foundation of every graph algorithm that explores structure — BFS, DFS, shortest paths, minimum spanning trees, and flow networks all rely on it.