Chapter 11 Simple Graphs428
Figure 11.20 A graph where the edges of a spanning tree have been thickened.Theorem 11.10.6.Every connected graph contains a spanning tree.
Proof. SupposeGis a connected graph, so the graphGitself is a connected, span-
ning subgraph. So by WOP,Gmust have a minimum-edge connected, spanning
subgraph,T. We claimT is a spanning tree. SinceT is a connected, spanning
subgraph by definition, all we have to show is thatTis acyclic.
But suppose to the contrary thatT contained a cycleC. By Lemma 11.9.6,
an edgeeofC will not be a cut edge, so removing it would leave a connected,
spanning subgraph that was smaller thanT, contradicting the minimality toT.
11.10.4 Minimum Weight Spanning Trees
Spanning trees are interesting because they connect all the nodes of a graph using
the smallest possible number of edges. For example the spanning tree for the 6-
node graph shown in Figure 11.20 has 5 edges.
In many applications, there are numerical costs or weights associated with the
edges of the graph. For example, suppose the nodes of a graph represent buildings
and edges represent connections between them. The cost of a connection may vary
a lot from one pair of buildings or towns to another. Another example is where the
nodes represent cities and the weight of an edge is the distance between them: the
weight of the Los Angeles/New York City edge is much higher than the weight of
the NYC/Boston edge. Theweight of a graphis simply defined to be the sum of
the weights of its edges. For example, the weight of the spanning tree shown in
Figure 11.21 is 19.
Definition 11.10.7.Aminimum weight spanning tree(MST) of an edge-weighted
graphGis a spanning tree ofGwith the smallest possible sum of edge weights.
Is the spanning tree shown in Figure 11.21(a) an MST of the weighted graph
shown in Figure 11.21(b)? It actually isn’t, since the tree shown in Figure 11.22 is
also a spanning tree of the graph shown in Figure 11.21(b), and this spanning tree
has weight 17.