Section 8.7: Trees

Last updated
Save as PDF

Page ID: 220203

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\dsum}{\displaystyle\sum\limits} $

$ \newcommand{\dint}{\displaystyle\int\limits} $

$ \newcommand{\dlim}{\displaystyle\lim\limits} $

$ \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}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$\newcommand{\longvect}{\overrightarrow}$

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

Learning Objectives

Determine where a graph is a tree
Find a spanning tree for a graph

In graph theory, many real-world systems, such as communication networks, transportation routes, and organizational structures, can be represented using graphs. In many of these situations, it is important to connect all points efficiently without creating unnecessary loops (circuits). This leads to an important type of graph known as a tree.

Tree

A tree is a connected graph that contains no circuits.

In other words, it is a graph in which there is exactly one path between any two vertices. This property ensures that every connection is essential; removing any edge would disconnect the graph, while adding any additional edge would create a circuit.

Trees are especially useful because they represent the simplest way to connect a set of vertices. For example, a company might want to connect several offices using the least amount of wiring, or a computer network may need to ensure efficient communication without redundancy. In each case, a tree structure provides a solution that is both connected and minimal.

Properties of Trees

A tree is a connected graph (from definition).
A tree contains no circuits (from definition).
If a tree has $n$ vertices, then it must have exactly $n−1$ edges.
Every edge is a bridge.
There is exactly one path between any two vertices.

The relationship between the number of vertices and the number of edges highlights the efficiency of trees, as they use the smallest possible number of edges while still maintaining connectivity.

Trees also play a central role in many areas of mathematics and computer science. They are used in designing networks, organizing data (such as file systems and search algorithms), and solving optimization problems. As we continue our study of graph theory, trees will provide a foundation for understanding more advanced concepts, including spanning trees and minimum spanning trees.

Example #8.7.1 🤔

Determine whether the given graph is a tree.

$Homework 8.7.1.png$

✅ Solution:

Let's check the properties for a tree:

The graph is connected. $\color{Green} {\checkmark}$
The graph contains no circuits. $\color{Green} {\checkmark}$
The graph has 7 vertices and 6 edges. (Edges = Vertices − 1). $\color{Green} {\checkmark}$
Every edge is a bridge. $\color{Green} {\checkmark}$
There is exactly one path between any two vertices. $\color{Green} {\checkmark}$

Thus, the graph is a tree.

Note: The 4^th and 5^th properties will always be true, if the first three properties are true. Technically, there is no need to check for the last two properties then. However, if you notice a bridge at first glance, then it would be easier to recognize that the graph is not a tree.

Example #8.7.2 🤔

Determine whether the given graph is a tree.

$Homework 8.7.1.png$

✅ Solution:

Let's check the properties for a tree:

The graph is connected. $\color{Green} {\checkmark}$
The graph contains no circuits. $\color{Red} {✗}$.

Thus, the graph is not a tree, because C-E-J-C is a circuit. There is no need to verify any other properties from this point on.

Example #8.7.3 🤔

Determine whether the given graph is a tree.

$Homework 8.7.3.png$

✅ Solution:

Let's check the properties for a tree:

The graph is connected. $\color{Green} {\checkmark}$
The graph contains no circuits. $\color{Green} {\checkmark}$
The graph has 17 vertices and 16 edges. (Edges = Vertices − 1). $\color{Green} {\checkmark}$
Every edge is a bridge. $\color{Green} {\checkmark}$
There is exactly one path between any two vertices. $\color{Green} {\checkmark}$

Thus, the graph is a tree.

Example #8.7.4 🤔

Determine whether the given graph is a tree.

$Homework 8.7.4.png$

✅ Solution:

Let's check the properties for a tree:

The graph is connected. $\color{Red} {✗}$.

Thus, the graph is not a tree, since edge N-L is disconnected from the rest of the graph and cannot be reached by any of the other vertices, G, A, E, and S. There is no need to verify any other properties from this point on.

Example #8.7.5 🤔

Determine whether the given graph is a tree.

$Homework 8.7.3.png$

✅ Solution:

Let's check the properties for a tree:

The graph is connected. $\color{Green} {\checkmark}$
The graph contains no circuits. $\color{Green} {\checkmark}$
The graph has 14 vertices and 13 edges. (Edges = Vertices − 1). $\color{Green} {\checkmark}$
Every edge is a bridge. $\color{Green} {\checkmark}$
There is exactly one path between any two vertices. $\color{Green} {\checkmark}$

Thus, the graph is a tree.

Example #8.7.6 🤔

Determine whether the given graph is a tree.

$Example 8.7.6.png$

✅ Solution:

Let's check the properties for a tree:

The graph is connected. $\color{Red} {✗}$.

Thus, the graph is not a tree, since the graph is disconnected. Vertices A, B, C, D, and E cannot reach any of the vertices, F, G, H, I and J and vice-versa. There is no need to verify any other properties from this point on.

Trees provide a simple and efficient way to connect a set of vertices using the minimum number of edges. However, many real-world networks are more complex and contain circuits. This raises an important question: How can we simplify such networks while still maintaining connectivity? This leads to the concept of a spanning tree.

Spanning Tree

A spanning tree of a graph is a sub-graph that includes all the vertices of the original graph and forms a tree. In other words, it “spans” all the vertices while removing enough edges to eliminate any circuits. The result is a connected graph with no circuits that uses the minimum number of edges.

Spanning trees are important because they allow us to take a complex network and reduce it to its most efficient structure without losing connectivity. For example, in designing communication networks, electrical grids, or transportation systems, it is often desirable to connect all locations using the least amount of material or cost. A spanning tree provides a way to achieve this.

Every connected graph has at least one spanning tree, and a graph may have many different spanning trees. Each spanning tree will contain the same number of vertices as the original graph, but exactly $n-1$ edges, where $n$ is the number of vertices.

In summary, the transition from trees to spanning trees allows us to apply the simplicity and efficiency of tree structures to more complex graphs. By extracting a spanning tree from a graph, we preserve connectivity while eliminating unnecessary edges, making it a powerful tool in both theory and real-world applications.

Example #8.7.7 🤔

Find a spanning tree for the graph.

$Example 8.3.6.png$

✅ Solution:

The graph is not a tree. It has 4 vertices and 5 edges, whereas a tree with 4 vertices must have exactly 3 edges. Therefore, 2 edges must be removed to form a tree. In this example, there will be 8 different possible spanning trees:

$Example 8.7.7b.png$ $Example 8.7.7c.png$ $Example 8.7.7d.png$ $Example 8.7.7e.png$ $Example 8.7.7f.png$ $Example 8.7.7g.png$ $Example 8.7.7h.png$ $Example 8.7.7i.png$

We are only interested in selecting one of these possible graphs to serve as a spanning tree. We are not concerned with determining how many spanning trees exist or identifying all of them.

Example #8.7.8 🤔

Find a spanning tree for the graph.

$Example 8.3.6.png$

✅ Solution:

The graph is not a tree. It has 6 vertices and 10 edges, whereas a tree with 6 vertices must have exactly 5 edges. Therefore, 5 edges must be removed to form a tree. Answers will vary. One possible solution:

$Example 8.7.8b.png$

Example #8.7.9 🤔

Find a spanning tree for the graph.

$Example 8.7.9.png$

✅ Solution:

The graph is not a tree. It has 7 vertices and 12 edges, whereas a tree with 7 vertices must have exactly 6 edges. Therefore, 6 edges must be removed to form a tree. Answers will vary. One possible solution:

$Example 8.7.9b.png$

Example #8.7.10 🤔

Find a spanning tree for the graph.

$Example 8.7.10.png$

✅ Solution:

The graph is not a tree. It has 8 vertices and many edges (28), whereas a tree with 8 vertices must have exactly 7 edges. Therefore, remove as many edges until only 7 edges are remaining to form a tree. Answers will vary. One possible solution:

$Example 8.7.10b.png$

Section 8.7: Trees [In-Class Exercises]

Determine whether the given graph is a tree.

$Exercise 8.7.1.png$

Determine whether the given graph is a tree.

$Exercise 8.7.2.png$

Determine whether the given graph is a tree.

$Exercise 8.7.3.png$

Determine whether the given graph is a tree.

$Exercise 8.7.4.png$

Determine whether the given graph is a tree.

$Exercise 8.7.5.png$

Determine whether the given graph is a tree.

$Exercise 8.7.6.png$

Determine whether the given graph is a tree.

$Exercise 8.7.7.png$

Find a spanning tree for the graph.

$Exercise 8.7.8.png$

Find a spanning tree for the graph.

$Exercise 8.7.9.png$

Find a spanning tree for the graph.

$Exercise 8.7.10.png$

Find a spanning tree for the graph.

$Exercise 8.7.11.png$

Find a spanning tree for the graph.

$Exercise 8.7.12.png$

Answers

Yes, it is a tree.
No, it is not a tree.
No, it is not a tree.
No, it is not a tree.
Yes, it is a tree.
No, it is not a tree.
Yes, it is a tree.
Any of these graphs will be a spanning tree: $Exercise 8.7.8b.png$ $Exercise 8.7.8c.png$ $Exercise 8.7.8c.png$ $Exercise 8.7.8e.png$
Either of these graphs will be a spanning tree: $Exercise 8.7.9b.png$ $Exercise 8.7.9c.png$
Answers will vary. One possible example: $Exercise 8.7.10b.png$
Answers will vary. One possible example: $Exercise 8.7.11b.png$
Answers will vary. One possible example: $Exercise 8.7.12b.png$

Search

Text Color

Text Size

Margin Size

Font Type

✅ Solution:

✅ Solution:

✅ Solution:

✅ Solution:

✅ Solution:

✅ Solution:

✅ Solution:

✅ Solution:

✅ Solution:

✅ Solution: