5.7: Connectivity
( \newcommand{\kernel}{\mathrm{null}\,}\)
We have seen examples of connected graphs and graphs that are not connected. While "not connected'' is pretty much a dead end, there is much to be said about "how connected'' a connected graph is. The simplest approach is to look at how hard it is to disconnect a graph by removing vertices or edges. We assume that all graphs are simple.
If it is possible to disconnect a graph by removing a single vertex, called a cutpoint, we say the graph has connectivity 1. If this is not possible, but it is possible to disconnect the graph by removing two vertices, the graph has connectivity 2.
If a graph G is connected, any set of vertices whose removal disconnects the graph is called a cutset. G has connectivity k if there is a cutset of size k but no smaller cutset. If there is no cutset and G has at least two vertices, we say G has connectivity n−1; if G has one vertex, its connectivity is undefined. If G is not connected, we say it has connectivity 0. G is k-connected if the connectivity of G is at least k. The connectivity of G is denoted κ(G).
As you should expect from the definition, there are graphs without a cutset: the complete graphs Kn. If G is connected but not a Kn, it has vertices v and w that are not adjacent, so removing the n−2 other vertices leaves a non-connected graph, and so the connectivity of G is at most n−2. Thus, only the complete graphs have connectivity n−1.
We do the same thing for edges:
If a graph G is connected, any set of edges whose removal disconnects the graph is called a cut. G has edge connectivity k if there is a cut of size k but no smaller cut; the edge connectivity of a one-vertex graph is undefined. G is k-edge-connected if the edge connectivity of G is at least k. The edge connectivity is denoted λ(G).
Any connected graph with at least two vertices can be disconnected by removing edges: by removing all edges incident with a single vertex the graph is disconnected. Thus, λ(G)≤δ(G), where δ(G) is the minimum degree of any vertex in G. Note that δ(G)≤n−1, so λ(G)≤n−1.
Removing a vertex also removes all of the edges incident with it, which suggests that κ(G)≤λ(G). This turns out to be true, though not as easy as you might hope. We write G−v to mean G with vertex v removed, and G−{v1,v2,…,vk} to mean G with all of {v1,v2,…,vk} removed, and similarly for edges.
κ(G)≤λ(G).
- Proof
-
We use induction on λ=λ(G). If λ=0, G is disconnected, so κ=0. If λ=1, removal of edge e with endpoints v and w disconnects G. If v and w are the only vertices of G, G is K2 and has connectivity 1. Otherwise, removal of one of v and w disconnects G, so κ=1.
As a special case we note that if λ=n−1 then δ=n−1, so G is Kn and κ=n−1.
Now suppose n−1>λ=k>1, and removal of edges e1,e2,…,ek disconnects G. Remove edge ek with endpoints v and w to form G1 with λ(G1)=k−1. By the induction hypothesis, there are at most k−1 vertices v1,v2,…,vj such that G2=G1−{v1,v2,…,vj} is disconnected. Since k<n−1, k−1≤n−3, and so G2 has at least 3 vertices.
If both v and w are vertices of G2, and if adding ek to G2 produces a connected graph G3, then removal of one of v and w will disconnect G3 forming G4, and G4=G−{v1,v2,…,vj,v} or G4=G−{v1,v2,…,vj,w}, that is, removing at most k vertices disconnects G. If v and w are vertices of G2 but adding ek does not produce a connected graph, then removing v1,v2,…,vj disconnects G. Finally, if at least one of v and w is not in G2, then G2=G−{v1,v2,…,vj} and the connectivity of G is less than k. So in all cases, κ≤k.
Graphs that are 2-connected are particularly important, and the following simple theorem is useful.
If G has at least three vertices, the following are equivalent:
- G is 2-connected
- G is connected and has no cutpoint
- For all distinct vertices u, v, w in G there is a path from u to v that does not contain w.
- Proof
-
1⇒3: Since G is 2-connected, G with w removed is a connected graph G′. Thus, in G′ there is a path from u to v, which in G is a path from u to v avoiding w.
3⇒2: If G has property 3 it is clearly connected. Suppose that w is a cutpoint, so that G′=G−w is disconnected. Let u and v be vertices in two different components of G′, so that no path connects them in G′. Then every path joining u to v in G must use w, a contradiction.
2⇒1: Since G has at least 3 vertices and has no cutpoint, its connectivity is at least 2, so it is 2-connected by definition.
There are other nice characterizations of 2-connected graphs.
If G has at least three vertices, then G is 2-connected if and only if every two vertices u and v are contained in a cycle.
- Proof
-
if: Suppose vertex w is removed from G, and consider any other vertices u and v. In G, u and v lie on a cycle; even if w also lies on this cycle, then u and v are still connected by a path when w is removed.
only if: Given u and v we want to show there is a cycle containing both. Let U be the set of vertices other than u that are contained in a cycle with u. First, we show that U is non-empty. Let w be adjacent to u, and remove the edge e between them. Since λ(G)≥κ(G)≥2, G−e is connected. Thus, there is a path from u to w; together with e this path forms a cycle containing u and w, so w∈U.
For a contradiction, suppose v∉U. Let w be in U with d(w,v)≥1 as small as possible, fix a cycle C containing u and w and a path P of length d(w,v) from w to v. By the previous theorem, there is a path Q from u to v that does not use w. Following this path from u, there is a last vertex x on the path that is also on the cycle containing u and w, and there is a first vertex y on the path, after x, with y also on the path from w to v (it is possible that y=v, but not that y=w); see Figure 5.7.1. Now starting at u, proceeding on cycle C to x without using w, then from x to y on Q, then to w on P, and finally back to u on C, we see that y∈U. But y is closer to v than is w, a contradiction. Hence v∈U.

The following corollary is an easy restatement of this theorem.
If G has at least three vertices, then G is 2-connected if and only if between every two vertices u and v there are two internally disjoint paths between v and w, that is, paths that share only the vertices v and w.
This version of the theorem suggests a generalization:
If G has at least k+1 vertices, then G is k-connected if and only if between every two vertices u and v there are k pairwise internally disjoint paths.
- Proof
-
Suppose first that between every two vertices v and w in G there are k internally disjoint paths. If G is not k-connected, the connectivity of G is at most k−1, and because G has at least k+1 vertices, there is a cutset S of G with size at most k−1. Let v and w be vertices in two different components of G−S; in G these vertices are joined by k internally disjoint paths. Since there is no path from v to w in G−S, each of these k paths contains a vertex of S, but this is impossible since S has size less than k, and the paths share no vertices other than v and w. This contradiction shows that G is k-connected.
Now suppose G is k-connected.
If v and w are not adjacent, κG(v,w)≥k and by the previous theorem there are pG(v,w)=κG(v,w) internally disjoint paths between v and w.
If v and w are connected by edge e, consider G−e. If there is a cutset of G−e of size less than k−1, call it S, then either S∪{v} or S∪{w} is a cutset of G of size less than k, a contradiction. (Since G has at least k+1 vertices, G−S has at least three vertices.) Thus, κG−e(v,w)≥k−1 and by the previous theorem there are at least k−1 internally disjoint paths between v and w in G−e. Together with the path v, w using edge e, these form k internally disjoint paths between v and w in G.
We first prove Menger's original version of this, a "local'' version.
If v and w are non-adjacent vertices in G, κG(v,w) is the smallest number of vertices whose removal separates v from w, that is, disconnects G leaving v and w in different components. A cutset that separates v and w is called a separating set for v and w. pG(v,w) is the maximum number of internally disjoint paths between v and w.
If v and w are non-adjacent vertices in G, κG(v,w)=pG(v,w).
- Proof
-
If there are k internally disjoint paths between v and w, then any set of vertices whose removal separates v from w must contain at least one vertex from each of the k paths, so κG(v,w)≥pG(v,w).
To finish the proof, we show that there are κG(v,w) internally disjoint paths between v and w. The proof is by induction on the number of vertices in G. If G has two vertices, G is not connected, and κG(v,w)=pG(v,w)=0. Now suppose G has n>2 vertices and κG(v,w)=k.
Note that removal of either N(v) or N(w) separates v from w, so no separating set S of size k can properly contain N(v) or N(w). Now we address two cases:
Case 1: Suppose there is a set S of size k that separates v from w, and S contains a vertex not in N(v) or N(w). G−S is disconnected, and one component G1 contains v. Since S does not contain N(v), G1 has at least two vertices; let X=V(G1) and Y=V(G)−S−X. Since S does not contain N(w), Y contains at least two vertices. Now we form two new graphs: Form HX by starting with G−Y and adding a vertex y adjacent to every vertex of S. Form HY by starting with G−X and adding a vertex x adjacent to every vertex of S; see Figure 5.7.2. Since X and Y each contain at least two vertices, HX and HY are smaller than G, and so the induction hypothesis applies to them.
Clearly S separates v from y in HX and w from x in HY. Moreover, any set that separates v from y in HX separates v from w in G, so κHX(v,y)=κG(v,w)=k. Similarly, κHY(x,w)=κG(v,w)=k. Hence, by the induction hypothesis, there are k internally disjoint paths from v to y in HX and k internally disjoint paths from x to w in HY. Each of these paths uses one vertex of S; by eliminating x and y and joining the paths at the vertices of S, we produce k internally disjoint paths from v to w.
Figure 5.7.2: Case 1: Top figure is G, lower left is HX, lower right is HY. Case 2: Now we suppose that any set S separating v and w is a subset of N(v)∪N(w); pick such an S. If there is a vertex u not in {v,w}∪N(v)∪N(w), consider G−u. This u is not in any set of size k that separates v from w, for if it were we would be in Case 1. Since S separates v from w in G−u, κG−u(v,w)≤k. But if some smaller set S′ separates v from w in G−u, then S′∪{u} separates v from w in G, a contradiction, so κG−u(v,w)=k. By the induction hypothesis, there are k internally disjoint paths from v to w in G−u and hence in G.
We are left with V(G)={v,w}∪N(v)∪N(w). Suppose there is a vertex u in N(v)∩N(w). Then u is in every set that separates v from w, so κG−u=k−1. By the induction hypothesis, there are k−1 internally disjoint paths from v to w in G−u and together with the path v,u,w, they comprise k internally disjoint paths from v to w in G. Finally, suppose that N(v)∩N(w)=∅. Form a bipartite graph B with vertices N(v)∪N(w) and any edges of G that have one endpoint in N(v) and the other in N(w). Every set separating v from w in G must include one endpoint of every edge in B, that is, must be a vertex cover in B, and conversely, every vertex cover in B separates v from w in G. Thus, the minimum size of a vertex cover in B is k, and so there is a matching in B of size k, by Theorem 4.6.4. The edges of this matching, together with the edges incident at v and w, form k internally disjoint paths from v to w in G.
∙∙∙
We return briefly to 2-connectivity. The next theorem can sometimes be used to provide the induction step in an induction proof.
Suppose G is 2-connected and K is a 2-connected proper subgraph of G. Then there are subgraphs L and H (the handle) of G such that L is 2-connected, L contains K, H is a simple path, L and H share exactly the endpoints of H, and G is the union of L and H.
- Proof
-
Given G and K, let L be a maximal proper subgraph of G containing K. If V(L)=V(G), let e be an edge not in L. Since L plus the edge e is 2-connected, it must be G, by the maximality of L. Hence H is the path consisting of e and its endpoints.
Suppose that v is in V(G) but not V(L). Let u be a vertex of L. Since G is 2-connected, there is a cycle containing v and u. Following the cycle from v to u, Let w be the first vertex in L. Continuing on the cycle from u to v, let x be the last vertex in L. Let P be the path continuing around the cycle: (x,v1,v2,…,vk,v=vk+1,vk+2,…,vm,w). If x≠w, let H=P. Since L together with H is 2-connected, it is G, as desired.
If x=w then x=w=u. Let y be a vertex of L other than u. Since G is 2-connected, there is a path P1 from v to y that does not include u. Let vj be the last vertex on P1 that is in {v1,…,v,…,vm}; without loss of generality, suppose j≥k+1. Then let H be the path (u,v1,…,v=vk+1,…,vj,…,y), where from vj to y we follow path P1. Now L∪H is a 2-connected subgraph of G, but it is not G, as it does not contain the edge {u,vm}, contradicting the maximality of L. Thus x≠w.
A graph that is not connected consists of connected components. In a theorem reminiscent of this, we see that connected graphs that are not 2-connected are constructed from 2-connected subgraphs and bridges.
A block in a graph G is a maximal induced subgraph on at least two vertices without a cutpoint.
As usual, maximal here means that the induced subgraph B cannot be made larger by adding vertices edges. A block is either a 2-connected induced subgraph or a single edge together with its endpoints. Blocks are useful in large part because of this theorem:
The blocks of G partition the edges.
- Proof
-
We need to show that every edge is in exactly one block. If an edge is in no 2-connected induced subgraph of G, then, together with its endpoints, it is itself a block. Thus, every edge is in some block.
Now suppose that B1 and B2 are distinct blocks. This implies that neither is a subgraph of the other, by the maximality condition. Hence, the induced subgraph G[V(B1)∪V(B2)] is larger than either of B1 and B2. Suppose B1 and B2 share an edge, so that they share the endpoints of this edge, say u and v. Supppose w is a vertex in V(B1)∪V(B2). Since B1−w and B2−w are connected, so is G[(V(B1)∪V(B2))∖{w}], because either u or v is in (V(B1)∪V(B2))∖{w}. Thus G[V(B1)∪V(B2)] has no cutpoint and so it is 2-connected and strictly contains B1 and B2, contradicting the maximality property of blocks. Thus, every edge is in at most one block.
If G has a single block, it is either K2 or is 2-connected, and any 2-connected graph has a single block.
If G is connected but not 2-connected, then every vertex that is in two blocks is a cutpoint of G.
- Proof
-
Suppose w is in B1 and B2, but G−w is connected. Then there is a path v1,v2,…,vk in G−w, with v1∈B1 and vk∈B2. But then G[V(B1)∪V(B2)∪{v1,v2,…,vk}] is 2-connected and contains both B1 and B2, a contradiction.