8 Trees
8.1 How to Define Trees
We have met trees when we were studying enumeration problems; now we
take a look at them as graphs. A graphG=(V, E) is called atreeif it
is connected and contains no cycle as a subgraph. The simplest tree has
one node and no edges. The second simplest tree consists of two nodes
connected by an edge. Figure 8.1 shows a variety of other trees.
FIGURE 8.1. Five trees.Note that the two properties defining trees work in opposite directions:
Connectedness means that the graph cannot have “too few” edges, while
the exclusion of cycles means that it cannot have “too many.” To be more
precise, if a graph is connected, then if add a new edge to it, it remains
connected (while if we delete an edge, it may become disconnected). If a
graph contains no cycle, then if we delete any edge, the remaining graph