Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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.

Definition 5.7.1: 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 n1; 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 n2 other vertices leaves a non-connected graph, and so the connectivity of G is at most n2. Thus, only the complete graphs have connectivity n1.

We do the same thing for edges:

Definition 5.7.2: 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 λ(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)n1, so λ(G)n1.

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 Gv 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.

Theorem 5.7.1

κ(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 λ=n1 then δ=n1, so G is Kn and κ=n1.

Now suppose n1>λ=k>1, and removal of edges e1,e2,,ek disconnects G. Remove edge ek with endpoints v and w to form G1 with λ(G1)=k1. By the induction hypothesis, there are at most k1 vertices v1,v2,,vj such that G2=G1{v1,v2,,vj} is disconnected. Since k<n1, k1n3, 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.

Theorem 5.7.2

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

13: 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.

32: If G has property 3 it is clearly connected. Suppose that w is a cutpoint, so that G=Gw 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.

21: 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.

Theorem 5.7.3

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, Ge is connected. Thus, there is a path from u to w; together with e this path forms a cycle containing u and w, so wU.

For a contradiction, suppose vU. 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 yU. But y is closer to v than is w, a contradiction. Hence vU.

clipboard_e66bb59130c94395d52f6ee79cca8db54.png
Figure 5.7.1: Point y closer to v than w is a contradition; path Q is shown dashed. (See Theorem 5.7.3.)

The following corollary is an easy restatement of this theorem.

Corollary 5.7.1

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.4: 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.

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 k1, and because G has at least k+1 vertices, there is a cutset S of G with size at most k1. Let v and w be vertices in two different components of GS; in G these vertices are joined by k internally disjoint paths. Since there is no path from v to w in GS, 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 Ge. If there is a cutset of Ge of size less than k1, 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, GS has at least three vertices.) Thus, κGe(v,w)k1 and by the previous theorem there are at least k1 internally disjoint paths between v and w in Ge. 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.

Definition 5.7.3: Separating Set

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.

Theorem 5.7.5

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). GS 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)SX. Since S does not contain N(w), Y contains at least two vertices. Now we form two new graphs: Form HX by starting with GY and adding a vertex y adjacent to every vertex of S. Form HY by starting with GX 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.

clipboard_e9415816fde712537981e0184140e9a11.png
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 Gu. 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 Gu, κGu(v,w)k. But if some smaller set S separates v from w in Gu, then S{u} separates v from w in G, a contradiction, so κGu(v,w)=k. By the induction hypothesis, there are k internally disjoint paths from v to w in Gu 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 κGu=k1. By the induction hypothesis, there are k1 internally disjoint paths from v to w in Gu 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.

Theorem 5.7.6: 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,v1,v2,,vk,v=vk+1,vk+2,,vm,w). If xw, 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 jk+1. Then let H be the path (u,v1,,v=vk+1,,vj,,y), where from vj to y we follow path P1. Now LH 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 xw.

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.4: 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.7

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 B1w and B2w 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.

Theorem 5.7.8

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 Gw is connected. Then there is a path v1,v2,,vk in Gw, with v1B1 and vkB2. But then G[V(B1)V(B2){v1,v2,,vk}] is 2-connected and contains both B1 and B2, a contradiction.


This page titled 5.7: Connectivity is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?