a graph t is called a tree if t is connected and t has no cycles. examples of trees are shown in fig. 8-17.
a forest g is a graph with no cycles hence the connected components of a forest g are trees. a graph without
cycles is said to be cycle-free. the tree consisting of a single vertex with no edges is called the degenerate tree.
consider a tree t . clearly, there is only one simple path between two vertices of t otherwise, the two paths
would form a cycle. also:
(a) suppose there is no edge {u, v} in t and we add the edge e = {u, v} to t . then the simple path from u to v
in t and e will form a cycle hence t is no longer a tree.
(b) on the other hand, suppose there is an edge e = {u, v} in t , and we deleting e from t . then t is no longer
connected (since there cannot be a path from u to v) hence t is no longer a tree.
the following theorem (proved in problem 8.14) applies when our graphs are ?nite.
theorem 8.6: let g be a graph with n > 1 vertices. then the following are equivalent:
(i) g is a tree.
(ii) g is a cycle-free and has n ? 1 edges.
(iii) g is connected and has n ? 1 edges.
this theorem also tells us that a ?nite tree t with n vertices must have n ? 1 edges. for example, the tree in
has 9 vertices and 8 edges, and the tree in fig. 8-17(b) has 13 vertices and 12 edges.