Skip to main content
$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 5.7: Connectivity

• • Contributed by David Guichard
• Professor (Mathematics) at Whitman College

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

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.

Definition: Cutset

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 $$\kappa(G)$$.

As you should expect from the definition, there are graphs without a cutset: the complete graphs $$K_n$$. If $$G$$ is connected but not a $$K_n$$, 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:

Definition: Cut

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 $$\lambda(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, $$\lambda(G)\le \delta(G)$$, where $$\delta(G)$$ is the minimum degree of any vertex in $$G$$. Note that $$\delta(G)\le n-1$$, so $$\lambda(G)\le n-1$$.

Removing a vertex also removes all of the edges incident with it, which suggests that $$\kappa(G)\le\lambda(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-\{v_1,v_2,\ldots,v_k\}$$ to mean $$G$$ with all of $$\{v_1,v_2,\ldots,v_k\}$$ removed, and similarly for edges.

Theorem 5.7.3

$$\kappa(G)\le\lambda(G)$$.

Proof

We use induction on $$\lambda=\lambda(G)$$. If $$\lambda=0$$, $$G$$ is disconnected, so $$\kappa=0$$. If $$\lambda=1$$, removal of edge $$e$$ with endpoints $$v$$ and $$w$$ disconnects $$G$$. If $$v$$ and $$w$$ are the only vertices of $$G$$, $$G$$ is $$K_2$$ and has connectivity $$1$$. Otherwise, removal of one of $$v$$ and $$w$$ disconnects $$G$$, so $$\kappa=1$$.

As a special case we note that if $$\lambda=n-1$$ then $$\delta=n-1$$, so $$G$$ is $$K_n$$ and $$\kappa=n-1$$.

Now suppose $$n-1>\lambda=k>1$$, and removal of edges $$e_1,e_2,\ldots,e_k$$ disconnects $$G$$. Remove edge $$e_k$$ with endpoints $$v$$ and $$w$$ to form $$G_1$$ with $$\lambda(G_1)=k-1$$. By the induction hypothesis, there are at most $$k-1$$ vertices $$v_1,v_2,\ldots,v_j$$ such that $$G_2=G_1-\{v_1,v_2,\ldots,v_j\}$$ is disconnected. Since $$k< n-1$$, $$k-1\le n-3$$, and so $$G_2$$ has at least $$3$$ vertices.

If both $$v$$ and $$w$$ are vertices of $$G_2$$, and if adding $$e_k$$ to $$G_2$$ produces a connected graph $$G_3$$, then removal of one of $$v$$ and $$w$$ will disconnect $$G_3$$ forming $$G_4$$, and $$G_4=G-\{v_1,v_2,\ldots,v_j,v\}$$ or $$G_4=G-\{v_1,v_2,\ldots,v_j,w\}$$, that is, removing at most $$k$$ vertices disconnects $$G$$. If $$v$$ and $$w$$ are vertices of $$G_2$$ but adding $$e_k$$ does not produce a connected graph, then removing $$v_1,v_2,\ldots,v_j$$ disconnects $$G$$. Finally, if at least one of $$v$$ and $$w$$ is not in $$G_2$$, then $$G_2=G-\{v_1,v_2,\ldots,v_j\}$$ and the connectivity of $$G$$ is less than $$k$$. So in all cases, $$\kappa\le k$$.

$$\square$$

Graphs that are 2-connected are particularly important, and the following simple theorem is useful.

Theorem 5.7.4

If $$G$$ has at least three vertices, the following are equivalent:

1. $$G$$ is 2-connected
2. $$G$$ is connected and has no cutpoint
3. For all distinct vertices $$u$$, $$v$$, $$w$$ in $$G$$ there is a path from $$u$$ to $$v$$ that does not contain $$w$$.

Proof

$$\bf 1\Rightarrow3$$: 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$$.

$$\bf 3\Rightarrow2$$: 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.

$$\bf 2\Rightarrow1$$: Since $$G$$ has at least 3 vertices and has no cutpoint, its connectivity is at least 2, so it is 2-connected by definition.

$$\square$$

There are other nice characterizations of 2-connected graphs.

Theorem 5.7.5

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 $$\lambda(G)\ge \kappa(G)\ge 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\in U$$.

For a contradiction, suppose $$v\notin U$$. Let $$w$$ be in $$U$$ with $$\d(w,v)\ge 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\in U$$. But $$y$$ is closer to $$v$$ than is $$w$$, a contradiction. Hence $$v\in U$$.

$$\square$$

Figure 5.7.1. Point $$y$$ closer to $$v$$ than $$w$$ is a contradiction; path $$Q$$ is shown dashed. (See theorem 5.7.5.)

The following corollary is an easy restatement of this theorem.

Corollary 5.7.6

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:

Theorem 5.7.7: Menger's Theorem

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.

We first prove Menger's original version of this, a "local'' version.

Definition: separating set

If $$v$$ and $$w$$ are non-adjacent vertices in $$G$$, $$\kappa_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$$. $$p_G(v,w)$$ is the maximum number of internally disjoint paths between $$v$$ and $$w$$.

Theorem 5.7.9

If $$v$$ and $$w$$ are non-adjacent vertices in $$G$$, $$\kappa_G(v,w)=p_G(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 $$\kappa_G(v,w)\ge p_G(v,w)$$.

To finish the proof, we show that there are $$\kappa_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 $$\kappa_G(v,w)=p_G(v,w)=0$$. Now suppose $$G$$ has $$n>2$$ vertices and $$\kappa_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 $$G_1$$ contains $$v$$. Since $$S$$ does not contain $$N(v)$$, $$G_1$$ has at least two vertices; let $$X=V(G_1)$$ 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 $$H_X$$ by starting with $$G-Y$$ and adding a vertex $$y$$ adjacent to every vertex of $$S$$. Form $$H_Y$$ 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, $$H_X$$ and $$H_Y$$ are smaller than $$G$$, and so the induction hypothesis applies to them.

Clearly $$S$$ separates $$v$$ from $$y$$ in $$H_X$$ and $$w$$ from $$x$$ in $$H_Y$$. Moreover, any set that separates $$v$$ from $$y$$ in $$H_X$$ separates $$v$$ from $$w$$ in $$G$$, so $$\ds\kappa_{H_X}(v,y)=\kappa_G(v,w)=k$$. Similarly, $$\ds\kappa_{H_Y}(x,w)=\kappa_G(v,w)=k$$. Hence, by the induction hypothesis, there are $$k$$ internally disjoint paths from $$v$$ to $$y$$ in $$H_X$$ and $$k$$ internally disjoint paths from $$x$$ to $$w$$ in $$H_Y$$. 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 $$H_X$$, lower right is $$H_Y$$.

Case 2: Now we suppose that any set $$S$$ separating $$v$$ and $$w$$ is a subset of $$N(v)\cup N(w)$$; pick such an $$S$$. If there is a vertex $$u$$ not in $$\{v,w\}\cup N(v)\cup 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$$, $$\kappa_{G-u}(v,w)\le k$$. But if some smaller set $$S'$$ separates $$v$$ from $$w$$ in $$G-u$$, then $$S'\cup\{u\}$$ separates $$v$$ from $$w$$ in $$G$$, a contradiction, so $$\kappa_{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\}\cup N(v)\cup N(w)$$. Suppose there is a vertex $$u$$ in $$N(v)\cap N(w)$$. Then $$u$$ is in every set that separates $$v$$ from $$w$$, so $$\kappa_{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)\cap N(w)=\emptyset$$. Form a bipartite graph $$B$$ with vertices $$N(v)\cup 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.5.6. 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$$.

$$\square$$

Proof of Menger's Theorem

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, $$\kappa_G(v,w)\ge k$$ and by the previous theorem there are $$p_G(v,w)=\kappa_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\cup\{v\}$$ or $$S\cup\{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, $$\kappa_{G-e}(v,w)\ge 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$$.

$$\square$$

$$\bullet\quad\bullet\quad\bullet$$

We return briefly to 2-connectivity. The next theorem can sometimes be used to provide the induction step in an induction proof.

Theorem 5.7.10: The Handle Theorem

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,v_1,v_2,\ldots,v_k,v=v_{k+1},v_{k+2},\ldots,v_m,w)$$. If $$x\not=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 $$P_1$$ from $$v$$ to $$y$$ that does not include $$u$$. Let $$v_j$$ be the last vertex on $$P_1$$ that is in $$\{v_1,\ldots,v,\ldots,v_m\}$$; without loss of generality, suppose $$j\ge k+1$$. Then let $$H$$ be the path $$(u,v_1,\ldots,v=v_{k+1},\ldots, v_j,\ldots,y)$$, where from $$v_j$$ to $$y$$ we follow path $$P_1$$. Now $$L\cup H$$ is a 2-connected subgraph of $$G$$, but it is not $$G$$, as it does not contain the edge $$\{u,v_m\}$$, contradicting the maximality of $$L$$. Thus $$x\not=w$$.

$$\square$$

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.

Definition: Block

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:

Theorem 5.7.12

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 $$B_1$$ and $$B_2$$ are distinct blocks. This implies that neither is a subgraph of the other, by the maximality condition. Hence, the induced subgraph $$G[V(B_1)\cup V(B_2)]$$ is larger than either of $$B_1$$ and $$B_2$$. Suppose $$B_1$$ and $$B_2$$ share an edge, so that they share the endpoints of this edge, say $$u$$ and $$v$$. Supppose $$w$$ is a vertex in $$V(B_1)\cup V(B_2)$$. Since $$B_1-w$$ and $$B_2-w$$ are connected, so is $$G[(V(B_1)\cup V(B_2))\backslash\{w\}]$$, because either $$u$$ or $$v$$ is in $$(V(B_1)\cup V(B_2))\backslash\{w\}$$. Thus $$G[V(B_1)\cup V(B_2)]$$ has no cutpoint and so it is 2-connected and strictly contains $$B_1$$ and $$B_2$$, contradicting the maximality property of blocks. Thus, every edge is in at most one block.

$$\square$$

If $$G$$ has a single block, it is either $$K_2$$ or is 2-connected, and any 2-connected graph has a single block.

Theorem 5.7.13

If $$G$$ is connected but not 2-connected, then every vertex that is in two blocks is a cutpoint of $$G$$.

Note

Proof.
Suppose $$w$$ is in $$B_1$$ and $$B_2$$, but $$G-w$$ is connected. Then there is a path $$v_1,v_2,\ldots,v_k$$ in $$G-w$$, with $$v_1\in B_1$$ and $$v_k\in B_2$$. But then $$G[V(B_1)\cup V(B_2)\cup \{v_1,v_2,\ldots,v_k\}]$$ is 2-connected and contains both $$B_1$$ and $$B_2$$, a contradiction.

$$\square$$