5.7: Connectivity

Last updated
Save as PDF

Page ID: 7202

$guichard.png$
Contributed by David Guichard
Professor (Mathematics) at Whitman College

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\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]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\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]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

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:

$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

$\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$

Contributors and Attributions

David Guichard (Whitman College)