Page 706 - Discrete Mathematics and Its Applications

10.4 Connectivity 685

The graph G 2 has no cut edges, as the reader should verify, but the removal of the two edges
{a, b} and {a, c} disconnects it. Hence, λ(G 2 ) = 2. Similarly, λ(G 3 ) = 2, because G 3 has no
cut edges, but the removal of the two edges {b, c} and {f, g} disconnects it.
The reader should verify that the removal of no two edges disconnects G 4 , but the removal
of the three edges {b, c}, {a, f }, and {f, g} disconnects it. Hence, λ(G 4 ) = 3. Finally, the reader
should verify that λ(G 5 ) = 3, because the removal of any two of its edges does not disconnect
it, but the removal of {a, b}, {a, g}, and {a, h} does. ▲
AN INEQUALITY FOR VERTEX CONNECTIVITY AND EDGE CONNECTIVITY
When G = (V, E) is a noncomplete connected graph with at least three vertices, the minimum
degree of a vertex of G is an upper bound for both the vertex connectivity of G and the edge
connectivity of G. That is, κ(G) ≤ min v∈V deg(v) and λ(G) ≤ min v∈V deg(v). To see this,
observe that deleting all the neighbors of a fixed vertex of minimum degree disconnects G, and
deleting all the edges that have a fixed vertex of minimum degree as an endpoint disconnects G.
In Exercise 55, we ask the reader to show that κ(G) ≤ λ(G) when G is a connected non-
complete graph. Note also that κ(K n ) = λ(K n ) = min v∈V deg(v) = n − 1 when n is a positive
integer and that κ(G) = λ(G) = 0 when G is a disconnected graph. Putting these facts together,
establishes that for all graphs G,

κ(G) ≤ λ(G) ≤ min v∈V deg(v).

APPLICATIONS OF VERTEX AND EDGE CONNECTIVITY Graph connectivity plays
an important role in many problems involving the reliability of networks. For instance, as we
mentioned in our introduction of cut vertices and cut edges, we can model a data network using
vertices to represent routers and edges to represent links between them. The vertex connectivity
of the resulting graph equals the minimum number of routers that disconnect the network when
they are out of service. If fewer routers are down, data transmission between every pair of routers
is still possible. The edge connectivity represents the minimum number of fiber optic links that
can be down to disconnect the network. If fewer links are down, it will still be possible for data
to be transmitted between every pair of routers.
We can model a highway network, using vertices to represent highway intersections and
edges to represent sections of roads running between intersections.The vertex connectivity of the
resulting graph represents the minimum number of intersections that can be closed at a particular
time that makes it impossible to travel between every two intersections. If fewer intersections
are closed, travel between every pair of intersections is still possible. The edge connectivity
represents the minimum number of roads that can be closed to disconnect the highway network.
If fewer highways are closed, it will still be possible to travel between any two intersections.
Clearly, it would be useful for the highway department to take this information into account
when planning road repairs.

Connectedness in Directed Graphs

There are two notions of connectedness in directed graphs, depending on whether the directions
of the edges are considered.

DEFINITION 4 A directed graph is strongly connected if there is a path from a to b and from b to a whenever
a and b are vertices in the graph.

For a directed graph to be strongly connected there must be a sequence of directed edges
from any vertex in the graph to any other vertex. A directed graph can fail to be strongly
connected but still be in “one piece.” Definition 5 makes this notion precise.