Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

164 GRAPH THEORY [CHAP. 8

Fig. 8-16

8.8Tree Graphs

A graphTis called atreeifTis connected andThas no cycles. Examples of trees are shown in Fig. 8-17.
A forest Gis a graph with no cycles; hence the connected components of a forestGare trees. A graph without
cycles is said to becycle-free. The tree consisting of a single vertex with no edges is called thedegenerate tree.
Consider a treeT. Clearly, there is only one simple path between two vertices ofT; otherwise, the two paths
would form a cycle. Also:

(a) Suppose there is no edge{u, v}inTand we add the edgee={u, v}toT. Then the simple path fromutov

inTandewill form a cycle; henceTis no longer a tree.

(b) On the other hand, suppose there is an edgee={u, v}inT, and we deleteefromT. ThenTis no longer

connected (since there cannot be a path fromutov); henceTis no longer a tree.

The following theorem (proved in Problem 8.14) applies when our graphs are finite.

Theorem 8.6: LetGbe a graph withn>1 vertices. Then the following are equivalent:

(i) Gis a tree.

(ii) Gis a cycle-free and hasn−1 edges.

(iii) Gis connected and hasn−1 edges.

This theorem also tells us that a finite treeTwithnvertices must haven−1 edges. For example, the tree in
Fig. 8-17(a)has9 vertices and 8 edges, and the tree in Fig. 8-17(b)has 13 vertices and 12 edges.

Fig. 8-17

Spanning Trees

A subgraphT of a connected graphGis called aspanning treeofGifTis a tree andTincludes all the
vertices ofG. Figure 8-18 shows a connected graphGand spanning treesT 1 ,T 2 , andT 3 ofG.