ABSTRACT
A tree is a connected graph that has no cycles. Figure 5.1 shows a number of trees.
FIGURE 5.1
Various trees
Trees are the smallest connected graphs; remove any edge from a tree and it
becomes disconnected. As well as being an important class of graphs, trees are im-
portant in computer science as data structures, and as objects constructed by search
algorithms. A fundamental property of trees is that all trees on n vertices have the same number of edges.