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 5.7.1 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)$. $\square$
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 5.7.2 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)$. $\square$
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$. $\qed$
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. $\qed$
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$. $\qed$
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, that is, paths that share only the vertices $u$ and $v$. $\qed$
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. $\square$
We first prove Menger's original version of this, a "local'' version.
Definition 5.7.8 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$. $\square$
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$.
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$. $\qed$
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$. Suppose there is a separating set $S$ for $v$ and $w$ with $|S|< k-1$, that is, $\kappa_{G-e}(v,w) < k-1$. $S$ cannot be a cutset for $G$, so $G-S$ is connected. Then $G-e-S$ must have exactly two components, since $G-S$ is $G-e-S$ plus a single edge. $G-e-S$ has at least $k+1-(k-2)=3$ vertices, so one of the two components contains at least two vertices; without loss of generality, say $u$ and $w$ are in a single component. Then $G-(S\cup\{w\})$ is not connected, but $|S\cup\{w\}|< k$, contradicting the assumption that $G$ is $k$-connected. Thus, $\kappa_{G-e}(v,w) \ge k-1$, so there are $k-1$ internally disjoint paths between $v$ and $w$ in $G-e$. Together with the path from $v$ to $w$ using $e$, this gives $k$ internally disjoint paths between $v$ and $w$ in $G$, as desired. $\qed$
$$\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$. $\qed$
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 5.7.11 A block in a graph $G$ is a maximal induced subgraph on at least two vertices without a cutpoint. $\square$
As usual, maximal here means that the induced subgraph $B$ cannot be made larger by adding vertices or edges (while retaining the desired property, in this case, no cutpoints). 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:
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 but strictly contains $B_1$ and $B_2$, contradicting the maximality property of blocks. Thus, every edge is in at most one block. $\qed$
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$.
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\}]$ has no cutpoint and contains both $B_1$ and $B_2$, a contradiction. $\qed$
Exercises 5.7
Ex 5.7.1 Suppose a simple graph $G$ on $n\ge 2$ vertices has at least $\ds {(n-1)(n-2)\over2}+1$ edges. Prove that $G$ is connected.
Ex 5.7.2 Suppose a general graph $G$ has exactly two odd-degree vertices, $v$ and $w$. Let $G'$ be the graph created by adding an edge joining $v$ to $w$. Prove that $G'$ is connected if and only if $G$ is connected.
Ex 5.7.3 Suppose $G$ is simple with degree sequence $d_1\le d_2\le\cdots\le d_n$, and for $k\le n-d_n-1$, $d_k\ge k$. Show $G$ is connected.
Ex 5.7.4 Recall that a graph is $k$-regular if all the vertices have degree $k$. What is the smallest integer $k$ that makes this true:
If $G$ is simple, has $n$ vertices, $m\ge k$, and $G$ is $m$-regular, then $G$ is connected.
(Of course $k$ depends on $n$.)
Ex 5.7.5 Suppose $G$ has at least one edge. Show that $G$ is 2-connected if and only if for all vertices $v$ and edges $e$ there is a cycle containing $v$ and $e$.
Ex 5.7.6 Find a simple graph with $\kappa(G)< \lambda(G)< \delta(G)$.
Ex 5.7.7 Suppose $\lambda(G)=k>0$. Show that there are sets of vertices $U$ and $V$ that partition the vertices of $G$, and such that there are exactly $k$ edges with one endpoint in $U$ and one endpoint in $V$.
Ex 5.7.8 Find $\lambda(K_{m,n})$, where both $m$ and $n$ are at least 1. ($K_{m,n}$ is the complete bipartite graph on $m$ and $n$ vertices: the parts have $m$ and $n$ vertices, and every pair of vertices, one from each part, is connected by an edge.)
Ex 5.7.9 Suppose $G$ is a connected graph. The block-cutpoint graph of $G$, $BC(G)$ is formed as follows: Let vertices $c_1,c_2,\ldots,c_k$ be the cutpoints of $G$, and let the blocks of $G$ be $B_1,\ldots,B_l$. The vertices of $BC(G)$ are $c_1,…,c_k,B_1,\ldots,B_l$. Add an edge $\{B_i,c_j\}$ if and only if $c_j\in B_i$. Show that the block-cutpoint graph is a tree.
Note that a cutpoint is contained in at least two blocks, so that all pendant vertices of the block-cutpoint graph are blocks. These blocks are called endblocks.
Ex 5.7.10 Draw the block-cutpoint graph of the graph below.
Ex 5.7.11 Show that the complement of a disconnected graph is connected. Is the complement of a connected graph always disconnected? (The complement $\overline G$ of graph $G$ has the same vertices as $G$, and $\{v,w\}$ is an edge of $\overline G$ if and only if it is not an edge of $G$.)