Skip to main content
Engineering LibreTexts

11.10: Forests and Trees

  • Page ID
    48375
    • Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
    • Google and Massachusetts Institute of Technology via MIT OpenCourseWare
    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    We’ve already made good use of digraphs without cycles, but simple graphs without cycles are arguably the most important graphs in computer science.

    Leaves, Parents & Children

    Definition: \(\PageIndex{1}\)

    An acyclic graph is called a forest. A connected acyclic graph is called a tree.

    The graph shown in Figure 11.17 is a forest. Each of its connected components is by definition a tree.

    One of the first things you will notice about trees is that they tend to have a lot of nodes with degree one. Such nodes are called leaves.

    Definition: \(\PageIndex{2}\)

    A degree 1 node in a forest is called a leaf.

    The forest in Figure 11.17 has 4 leaves. The tree in Figure 11.18 has 5 leaves.

    Trees are a fundamental data structure in computer science. For example, information is often stored in tree-like data structures, and the execution of many recursive programs can be modeled as the traversal of a tree. In such cases, it is often useful to arrange the nodes in levels, where the node at the top level is identified as the root and where every edge joins a parent to a child one level below. Figure 11.19 shows the tree of Figure 11.18 redrawn in this way. Node \(d\) is a child of node \(e\) and the parent of nodes \(b\) and \(c\).

    clipboard_ef88d0febe89f9327b84116b0904a47eb.png
    Figure 11.17 A 6-node forest consisting of 2 component trees.
    clipboard_e77bcc0e010d734bd99e3dd50056731f6.png
    Figure 11.18 A 9-node tree with 5 leaves.
    clipboard_e2c421b58e2d62d30cdc3b6999c42f87d.png
    Figure 11.19 The tree from Figure 11.18 redrawn with node e as the root and the other nodes arranged in levels.

    Properties

    Trees have many unique properties. We have listed some of them in the following theorem.

    Theorem \(\PageIndex{3}\)

    Every tree has the following properties:

    1. Every connected subgraph is a tree.
    2. There is a unique path between every pair of vertices.
    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 subgraph of an acyclic graph must also be acyclic. If the subgraph is also connected, then by definition, it is a tree.
    2. Since a tree is connected, there is at least one path between every pair of vertices. Suppose for the purposes of contradiction, that there are two different paths between some pair of vertices. Then there are two distinct paths \(\textbf{p} \neq \textbf{q}\) between the same two vertices with minimum total length \(|\textbf{p}| + |\textbf{q}|\). If these paths shared a vertex, \(w\), other than at the start and end of the paths, then the parts of \(\textbf{p}\) and \(\textbf{q}\) from start to \(w\), or the parts of \(\textbf{p}\) and \(\textbf{q}\) from \(w\) to the end, must be distinct paths between the same vertices with total length less than \(|\textbf{p}| + |\textbf{q}|\), contradicting the minimality of this sum. Therefore, \(\textbf{p}\) and \(\textbf{q}\) have no vertices in common besides their endpoints, and so \(\textbf{p} \hat{} \text{reverse}(\textbf{q})\) is a cycle.
    3. An additional edge b \(\langle u - v\rangle\) together with the unique path between \(u\) and \(v\) forms a cycle.
    4. Suppose that we remove edge \(\langle u - v\rangle\). Since the tree contained a unique path between \(u\) and \(v\), that path must have been \(\langle u - v\rangle\). Therefore, when that edge is removed, no path remains, and so the graph is not connected.
    5. Since the tree has at least two vertices, the longest path in the tree will have different endpoints \(u\) and \(v\). We claim \(u\) is a leaf. This follows because, since by definition of endpoint, \(u\) is incident to at most one edge on the path. Also, if \(u\) was incident to an edge not on the path, then the path could be lengthened by adding that edge, contradicting the fact that the path was as long as possible. It follows that \(u\) is incident only to a single edge, that is \(u\) is a leaf. The same hold for \(v\).
    6. We use induction on the proposition

    \[\nonumber P(n) ::= \text{there are } n - 1 \text{ edges in any } n-\text{vertex tree}.\]

    Base case (\(n = 1\)): \(P(n)\) is true since a tree with 1 node has 0 edges and \(1 - 1 = 0\).

    Inductive step: Now suppose that \(P(n)\) is true and consider an \(n+1\)-vertex tree, \(T\). Let \(v\) be a leaf of the tree. You can verify that deleting a vertex of degree 1 (and its incident edge) from any connected graph leaves a connected subgraph. So by Theorem 11.10.3.1, deleting \(v\) and its incident edge gives a smaller tree, and this smaller tree has \(n - 1\) edges by induction. If we reattach the vertex, \(v\), and its incident edge, we find that \(T\) has \(n = (n+1) - 1\) edges. Hence, \(P(n+1)\) is true, and the induction proof is complete. \(\quad \blacksquare\)

    Various subsets of properties in Theorem 11.10.3 provide alternative characterizations of trees. For example,

    Lemma 11.10.4. A graph \(G\) is a tree iff \(G\) is a forest and \(|V(G)| = |E(G)| + 1.\)

    The proof is an easy consequence of Theorem 11.9.7.6 (Problem 11.55).

    Spanning Trees

    Trees are everywhere. In fact, every connected graph contains a subgraph that is a tree with the same vertices as the graph. This is called a spanning tree for the graph. For example, Figure 11.20 is a connected graph with a spanning tree highlighted.

    clipboard_e96cf1211a61ec22b763c8fd5a41f8263.png
    Figure 11.20 A graph where the edges of a spanning tree have been thickened.

    Definition \(\PageIndex{5}\)

    Define a spanning subgraph of a graph, \(G\), to be a subgraph containing all the vertices of \(G\).

    Theorem \(\PageIndex{6}\)

    Every connected graph contains a spanning tree.

    Proof

    Suppose \(G\) is a connected graph, so the graph \(G\) itself is a connected, spanning subgraph. So by WOP, \(G\) must have a minimum-edge connected, spanning subgraph, \(T\). We claim \(T\) is a spanning tree. Since \(T\) is a connected, spanning subgraph by definition, all we have to show is that \(T\) is acyclic.

    But suppose to the contrary that \(T\) contained a cycle \(C\). By Lemma 11.9.6, an edge \(e\) of \(C\) will not be a cut edge, so removing it would leave a connected, spanning subgraph that was smaller than \(C\), contradicting the minimality to \(T\). \(\quad \blacksquare\)

    Minimum Weight Spanning Trees

    Spanning trees are interesting because they connect all the nodes of a graph using the smallest possible number of edges. For example the spanning tree for the 6- node graph shown in Figure 11.20 has 5 edges.

    In many applications, there are numerical costs or weights associated with the edges of the graph. For example, suppose the nodes of a graph represent buildings and edges represent connections between them. The cost of a connection may vary a lot from one pair of buildings or towns to another. Another example is where the nodes represent cities and the weight of an edge is the distance between them: the weight of the Los Angeles/New York City edge is much higher than the weight of the NYC/Boston edge. The weight of a graph is simply defined to be the sum of the weights of its edges. For example, the weight of the spanning tree shown in Figure 11.21 is 19.

    Definition \(\PageIndex{7}\)

    A minimum weight spanning tree (MST) of an edge-weighted graph \(G\) is a spanning tree of \(G\) with the smallest possible sum of edge weights.

    Is the spanning tree shown in Figure 11.21(a) an MST of the weighted graph shown in Figure 11.21(b)? It actually isn’t, since the tree shown in Figure 11.22 is also a spanning tree of the graph shown in Figure 11.21(b), and this spanning tree has weight 17.

    clipboard_e18106c882b256cbb92ff45108cfc1fe3.png
    Figure 11.21 A spanning tree (a) with weight 19 for a graph (b).
    clipboard_e9163a213bd008cbe16f3d3335618d93f.png
    Figure 11.22 An MST with weight 17 for the graph in Figure 11.21(b).

    What about the tree shown in Figure 11.22? It seems to be an MST, but how do we prove it? In general, how do we find an MST for a connected graph \(G\)? We could try enumerating all subtrees of \(G\), but that approach would be hopeless for large graphs.

    There actually are many good ways to find MST’s based on a property of some subgraphs of \(G\) called pre-MST’s.

    Definition \(\PageIndex{8}\)

    A pre-MST for a graph \(G\) is a spanning subgraph of \(G\) that is also a subgraph of some MST of \(G\).

    So a pre-MST will necessarily be a forest.

    For example, the empty graph with the same vertices as \(G\) is guaranteed to be a pre-MST of \(G\), and so is any actual MST of \(G\).

    If \(e\) is an edge of \(G\) and \(S\) is a spanning subgraph, we’ll write \(S + e\) for the spanning subgraph with edges \(E(S) \cup \{e\}\).

    Definition \(\PageIndex{9}\)

    If \(F\) is a pre-MST and \(e\) is a new edge, that is \(e \in E(G) - E(F)\), then \(e\) extends \(F\) when \(F + e\) is also a pre-MST.

    So being a pre-MST is contrived to be an invariant under addition of extending edges, by the definition of extension.

    The standard methods for finding MST’s all start with the empty spanning forest and build up to an MST by adding one extending edge after another. Since the empty spanning forest is a pre-MST, and being a pre-MST is, by definition, invariant under extensions, every forest built in this way will be a pre-MST. But no spanning tree can be a subgraph of a different spanning tree. So when the pre-MST finally grows enough to become a tree, it will be an MST. By Lemma 11.10.4, this happens after exactly \(|V(G)| - 1\) edge extensions.

    So the problem of finding MST’s reduces to the question of how to tell if an edge is an extending edge. Here’s how:

    Definition \(\PageIndex{10}\)

    Let \(F\) be a pre-MST, and color the vertices in each connected component of \(F\) either all black or all white. At least one component of each color is required. Call this a solid coloring of \(F\). A gray edge of a solid coloring is an edge of \(G\) with different colored endpoints.

    Any path in \(G\) from a white vertex to a black vertex obviously must include a gray edge, so for any solid coloring, there is guaranteed to be at least one gray edge. In fact, there will have to be at least as many gray edges as there are components with the same color. Here’s the punchline:

    Lemma 11.10.11. An edge extends a pre-MST \(F\) if it is a minimum weight gray edge in some solid coloring of \(F\).

    So to extend a pre-MST, choose any solid coloring, find the gray edges, and among them choose one with minimum weight. Each of these steps is easy to do, so it is easy to keep extending and arrive at an MST. For example, here are three known algorithms that are explained by Lemma 11.10.11:

    Algorithm 1. [Prim] Grow a tree one edge at a time by adding a minimum weight edge among the edges that have exactly one endpoint in the tree.

    This is the algorithm that comes from coloring the growing tree white and all the vertices not in the tree black. Then the gray edges are the ones with exactly one endpoint in the tree.

    Algorithm 2. [Kruskal] Grow a forest one edge at a time by adding a minimum weight edge among the edges with endpoints in different connected components.

    An edge does not create a cycle iff it connects different components. The edge chosen by Kruskal’s algorithm will be the minimum weight gray edge when the components it connects are assigned different colors.

    For example, in the weighted graph we have been considering, we might run Algorithm 1 as follows. Start by choosing one of the weight 1 edges, since this is the smallest weight in the graph. Suppose we chose the weight 1 edge on the bottom of the triangle of weight 1 edges in our graph. This edge is incident to the same vertex as two weight 1 edges, a weight 4 edge, a weight 7 edge, and a weight 3 edge. We would then choose the incident edge of minimum weight. In this case, one of the two weight 1 edges. At this point, we cannot choose the third weight 1 edge: it won’t be gray because its endpoints are both in the tree, and so are both colored white. But we can continue by choosing a weight 2 edge. We might end up with the spanning tree shown in Figure 11.23, which has weight 17, the smallest we’ve seen so far.

    clipboard_e144e9b379d036e1dc22136132f226c65.png
    Figure 11.23 A spanning tree found by Algorithm 1.

    Now suppose we instead ran Algorithm 2 on our graph. We might again choose the weight 1 edge on the bottom of the triangle of weight 1 edges in our graph. Now, instead of choosing one of the weight 1 edges it touches, we might choose the weight 1 edge on the top of the graph. This edge still has minimum weight, and will be gray if we simply color its endpoints differently, so Algorithm 2 can choose it. We would then choose one of the remaining weight 1 edges. Note that neither causes us to form a cycle. Continuing the algorithm, we could end up with the same spanning tree in Figure 11.23, though this will depend on the tie breaking rules used to choose among gray edges with the same minimum weight. For example, if the weight of every edge in \(G\) is one, then all spanning trees are MST’s with weight \(|V(G)| - 1\), and both of these algorithms can arrive at each of these spanning trees by suitable tie-breaking.

    The coloring that explains Algorithm 1 also justifies a more flexible algorithm which has Algorithm 1 as a special case:

    Algorithm 3. Grow a forest one edge at a time by picking any component and adding a minimum weight edge among the edges leaving that component.

    This algorithm allows components that are not too close to grow in parallel and independently, which is great for “distributed” computation where separate processors share the work with limited communication between processors.

    These are examples of greedy approaches to optimization. Sometimes greediness works and sometimes it doesn’t. The good news is that it does work to find the MST. Therefore, we can be sure that the MST for our example graph has weight 17, since it was produced by Algorithm 2. Furthermore we have a fast algorithm for finding a minimum weight spanning tree for any graph.

    Ok, to wrap up this story, all that’s left is the proof that minimal gray edges are extending edges. This might sound like a chore, but it just uses the same reasoning we used to be sure there would be a gray edge when you need it.

    Proof. (of Lemma 11.10.11)

    Let \(F\) be a pre-MST that is a subgraph of some MST \(M\) of \(G\), and suppose \(e\) is a minimum weight gray edge under some solid coloring of \(F\). We want to show that \(F + e\) is also a pre-MST.

    If \(e\) happens to be an edge of \(M\), then \(F + e\) remains a subgraph of \(M\), and so is a pre-MST.

    The other case is when \(e\) is not an edge of \(M\). In that case, \(M + e\) will be a connected, spanning subgraph. Also \(M\) has a path \(\textbf{p}\) between the different colored endpoints of \(e\), so \(M + e\) has a cycle consisting of \(e\) together with \(\textbf{p}\). Now \(\textbf{p}\) has both a black endpoint and a white one, so it must contain some gray edge \(g \neq e\). The trick is to remove \(g\) from \(M + e\) to obtain a subgraph \(M + e - g\). Since gray edges by definition are not edges of \(F\), the graph \(M + e - g\) contains \(F + e\). We claim that \(M + e - g\) is an MST, which proves the claim that \(e\) extends \(F\).

    To prove this claim, note that \(M + e\) is a connected, spanning subgraph, and \(g\) is on a cycle of \(M + e\), so by Lemma 11.9.6, removing \(g\) won’t disconnect anything. Therefore, \(M + e - g\) is still a connected, spanning subgraph. Moreover, \(M + e - g\) has the same number of edges as \(M\), so Lemma 11.10.4 implies that it must be a spanning tree. Finally, since \(e\) is minimum weight among gray edges,

    \[\nonumber w(M + e - g) = w(M) + w(e) - w(g) \leq w(M).\]

    This means that \(M + e - g\) is a spanning tree whose weight is at most that of an MST, which implies that \(M + e - g\) is also an MST. \(\quad \blacksquare\)

    Another interesting fact falls out of the proof of Lemma 11.10.11:

    Corollary 11.10.12. If all edges in a weighted graph have distinct weights, then the graph has a unique MST.

    The proof of Corollary 11.10.12 is left to Problem 11.70.


    This page titled 11.10: Forests and Trees is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer (MIT OpenCourseWare) .

    • Was this article helpful?