Discrete Mathematics for Computer Science

374 CHAPTER 6 Graph Theory

Theorem 2. Let T be a graph. T is a tree if and only if any two vertices of T are joined

by a unique path.

Proof.

(=•) Suppose T is a graph such that every pair of vertices is joined by a unique path. T

is connected, since each vertex pair has a path joining them. Furthermore, T is acyclic. For

example, suppose T were not acyclic. Let A and B be vertices on an existing cycle. A and

B have different paths between them, contradicting the assumption, so T must therefore

be acyclic.

(.=) Let T be a tree that satisfies the hypotheses. Clearly, T is connected, since there is a

path between any pair of vertices. If T is not acyclic, there are at least two vertices A and

B for which there are at least two paths from A to B, which is a contradiction. 0

Additional characterizations of trees will be given in the exercises (see Exercise 8 in

Section 6.13). Having so many different ways to think about trees can make some proofs

a lot easier: You can pick a characterization of trees that is convenient for the situation at

hand rather than having to use the original definition of a tree.

Spanning Trees

Recall that for a graph G = (V, E), a spanning subgraph is a subgraph H = (VI, El)

of G with V 1 = V. Obviously, every graph has a spanning subgraph-namely, the graph

itself. The subgraph of a graph consisting of just the vertex set and no edges is also a span-

ning subgraph. Obviously, no "smaller" subgraph, in terms of the number of edges in the

subgraph, can be a spanning subgraph than this subgraph with zero edges. The problem of

more interest is to find the smallest, in terms of the number of edges, connected spanning

subgraph of a connected graph. Clearly, such a graph must be a tree. This smallest con-

nected spanning subgraph, a spanning tree, can be found using the algorithm of Kruskal.

6.11.1 Kruskal's Algorithm

Kruskal's algorithm proceeds by examining the edges of the graph one at a time, in any

particular order. As an edge is examined, the algorithm determines whether a spanning tree

exists that contains the edge and all the previously chosen edges. It turns out that the only

condition the edge must satisfy to be added to the edges already chosen is that it does not

form a cycle with any subset of the edges already chosen. If an edge does not form a cycle

with any subset of the previously chosen edges, then it is included in the chosen edge set. If

the edge does form a cycle with some of the previously chosen edges, then it is not chosen,

and the next edge is examined. When all the edges of a graph have been examined, the

edges in the subgraph consisting of the chosen edges form a spanning tree.

Kruskal's algorithm is an example of the family of algorithms that try at each stage to

advance toward the goal as far as possible in a single step. The algorithms of this family

are known as greedy algorithms, and they sometimes-but not always-find the best pos-

sible solution. As we have just seen, in the case of Kruskal's algorithm, the best possible

outcome, a spanning tree, is always found.