Mathematics for Computer Science

Chapter 11 Simple Graphs332

a

b c f h i

e

d g

Figure 11.20 The tree from Figure 11.19 redrawn with nodeeas the root and the
other nodes arranged in levels.

u x y v

Figure 11.21 If there are two paths betweenuandv, the graph must contain a
cycle.

6. The number of vertices in a tree is one larger than the number of edges.

Proof. 1. A cycle in a subgraph is also a cycle in the whole graph, so any sub-
graph of an acyclic graph must also be acyclic. If the subgraph is also con-
nected, then by definition, it is a tree.

2. Since a tree is connected, there is at least one path between every pair of ver-
   tices. Suppose for the purposes of contradiction, that there are two different
   paths between some pair of verticesuandv. Beginning atu, letxbe the first
   vertex where the paths diverge, and letybe the next vertex they share. (For
   example, see Figure 11.21.) Then there are two paths fromxtoywith no
   common edges, which defines a cycle. This is a contradiction, since trees are
   acyclic. Therefore, there is exactly one path between every pair of vertices.


3. An additional edgehu—vitogether with the unique path betweenuandv
   forms a cycle.


4. Suppose that we remove edgehu—vi. Since the tree contained a unique path
   betweenuandv, that path must have beenhu—vi. Therefore, when that