Mathematics for Computer Science

Chapter 11 Simple Graphs426

a

b c f h i

e

d g

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

3. Adding an edge between nonadjacent nodes in a tree creates a graph with a
   cycle.


4. Removing any edge disconnects the graph. That is, every edge is a cut edge.


5. If the tree has at least two vertices, then it has at least two leaves.


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 vertices. Then there are two distinct pathsp¤q
   between the same two vertices with minimum total lengthjpjCjqj. If these
   paths shared a vertex,w, other than at the start and end of the paths, then
   the parts ofpandqfrom start tow, or the parts ofpandqfromwto the
   end, must be distinct paths between the same vertices with total length less
   thanjpjCjqj, contradicting the minimality of this sum. Therefore,pandq
   have no vertices in common besides their endpoints, and sopbreverse.q/is
   a cycle.


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