Page 705 - Discrete Mathematics and Its Applications

684 10 / Graphs

A subset V of the vertex set V of G = (V, E) is a vertex cut,or separating set,if G − V

is disconnected. For instance, in the graph in Figure 1, the set {b, c, e} is a vertex cut with three
vertices, as the reader should verify. We leave it to the reader (Exercise 51) to show that every
connected graph, except a complete graph, has a vertex cut. We define the vertex connectivity
of a noncomplete graph G, denoted by κ(G), as the minimum number of vertices in a vertex
cut.
κ is the lowercase Greek
WhenGisacompletegraph,ithasnovertexcuts,becauseremovinganysubsetofitsvertices
letter kappa.
and all incident edges still leaves a complete graph. Consequently, we cannot define κ(G) as the
minimum number of vertices in a vertex cut when G is complete. Instead, we set κ(K n ) = n − 1,
the number of vertices needed to be removed to produce a graph with a single vertex.
Consequently, for every graph G, κ(G) is minimum number of vertices that can be re-
moved from G to either disconnect G or produce a graph with a single vertex. We have
0 ≤ κ(G) ≤ n − 1if G has n vertices, κ(G) = 0 if and only if G is disconnected or G = K 1 ,
and κ(G) = n − 1 if and only if G is complete [see Exercise 52(a)].
The larger κ(G) is, the more connected we consider G to be. Disconnected graphs and K 1
have κ(G) = 0, connected graphs with cut vertices and K 2 have κ(G) = 1, graphs without cut
vertices that can be disconnected by removing two vertices and K 3 have κ(G) = 2, and so
on. We say that a graph is k-connected (or k-vertex-connected), if κ(G) ≥ k. A graph G is 1-
connected if it is connected and not a graph containing a single vertex; a graph is 2-connected, or
biconnected, if it is nonseparable and has at least three vertices. Note that if G is a k-connected
graph, then G is a j-connected graph for all j with 0 ≤ j ≤ k.

EXAMPLE 8 Find the vertex connectivity for each of the graphs in Figure 4.

Solution: Each of the five graphs in Figure 4 is connected and has more than vertex, so each
of these graphs has positive vertex connectivity. Because G 1 is a connected graph with a cut
vertex, as shown in Example 7, we know that κ(G 1 ) = 1. Similarly, κ(G 2 ) = 1, because c is a
cut vertex of G 2 .
The reader should verify that G 3 has no cut vertices. but that {b, g} is a vertex cut. Hence,
κ(G 3 ) = 2. Similarly, because G 4 has a vertex cut of size two, {c, f }, but no cut vertices. It
follows that κ(G 4 ) = 2. The reader can verify that G 5 has no vertex cut of size two, but {b, c, f }
is a vertex cut of G 5 . Hence, κ(G 5 ) = 3. ▲

EDGE CONNECTIVITY We can also measure the connectivity of a connected graph G =
(V, E) in terms of the minimum number of edges that we can remove to disconnect it. If a graph
has a cut edge, then we need only remove it to disconnect G.If G does not have a cut edge,
we look for the smallest set of edges that can be removed to disconnect it. A set of edges E

is called an edge cut of G if the subgraph G − E is disconnected. The edge connectivity
λ is the lowercase Greek
of a graph G, denoted by λ(G), is the minimum number of edges in an edge cut of G. This
letter lambda.
defines λ(G) for all connected graphs with more than one vertex because it is always possible
to disconnect such a graph by removing all edges incident to one of its vertices. Note that
λ(G) = 0if G is not connected. We also specify that λ(G) = 0if G is a graph consisting of a
single vertex. It follows that if G is a graph with n vertices, then 0 ≤ λ(G) ≤ n − 1. We leave
it to the reader [Exercise 52(b)] to show that λ(G) = n − 1 where G is a graph with n vertices
if and only if G = K n , which is equivalent to the statement that λ(G) ≤ n − 2 when G is not a
complete graph.

EXAMPLE 9 Find the edge connectivity of each of the graphs in Figure 4.

Solution: Each of the five graphs in Figure 4 is connected and has more than one vertex, so we
know that all of them have positive edge connectivity. As we saw in Example 7, G 1 has a cut
edge, so λ(G 1 ) = 1.