Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section10.1What Is a Tree?

What distinguishes trees from other types of graphs is the absence of certain paths called cycles. Recall that a path is a sequence of consecutive edges in a graph, and a circuit is a path that begins and ends at the same vertex.

Definition10.1.1Cycle

A cycle is a circuit whose edge list contains no duplicates. It is customary to use \(C_n\) to denote a cycle with \(n\) edges.

The simplest example of a cycle in an undirected graph is a pair of vertices with two edges connecting them. Since trees are cycle-free, we can rule out all multigraphs from consideration as trees.

Trees can either be undirected or directed graphs. We will concentrate on the undirected variety in this chapter.

Definition10.1.2Tree

An undirected graph is a tree if it is connected and contains no cycles or self-loops.

Example10.1.3Some trees and non-trees
Some trees and some non-trees
Figure10.1.4Some trees and some non-trees

  1. Graphs i, ii and iii in Figure 10.1.4 are all trees, while graphs iv, v, and vi are not trees.

  2. A \(K_2\) is a tree. However, if \(n\geq 3\), a \(K_n\) is not a tree.

  3. In a loose sense, a botanical tree is a mathematical tree. There are usually no cycles in the branch structure of a botanical tree.

  4. The structures of some chemical compounds are modeled by a tree. For example, butane 10.1.5.(a) consists of four carbon atoms and ten hydrogen atoms, where an edge between two atoms represents a bond between them. A bond is a force that keeps two atoms together. The same set of atoms can be linked together in a different tree structure to give us the compound isobutane 10.1.5.(b). There are some compounds whose graphs are not trees. One example is benzene 10.1.5.(c).

Structure of Butane
Structure of Isobutane
Structure of Benzene
(a)Butane
(b)Isobutane
(c)Benzene
Figure10.1.5The structure of some organic compounds

One type of graph that is not a tree, but is closely related, is a forest.

Definition10.1.6Forest

A forest is an undirected graph whose components are all trees.

Example10.1.7A forest

The top half of Figure 10.1.4 can be viewed as a forest of three trees. Graph (vi) in this figure is also a forest.

We will now examine several conditions that are equivalent to the one that defines a tree. The following theorem will be used as a tool in proving that the conditions are equivalent.

Proof

The usual definition of a directed tree is based on whether the associated undirected graph, which is created by “erasing” its directional arrows, is a tree. In Section 10.3 we will introduce the rooted tree, which is a special type of directed tree.

Subsection10.1.1Exercises for Section 10.1

1

Given the following vertex sets, draw all possible undirected trees that connect them.

  1. \(V_a= \{\text{right},\text{left}\}\)

  2. \(V_b = \{+,-,0\}\)

  3. \(V_c = \{\text{north}, \text{south}, \text{east}, \text{west}\}\).

Answer
2

Are all trees planar? If they are, can you explain why? If they are not, you should be able to find a nonplanar tree.

3

Prove that if \(G\) is a simple undirected graph with no self-loops, then \(G\) is a tree if and only if \(G\) is connected and \(\lvert E \rvert = \lvert V \rvert - 1\).

Hint
4

  1. Prove that if \(G = (V, E)\) is a tree and \(e \in E\), then \((V, E - \{e\})\) is a forest of two trees.

  2. Prove that if \(\left(V_1,E_1\right.\)) and \(\left(V_2,E_2\right)\) are disjoint trees and \(e\) is an edge that connects a vertex in \(V_1\) to a vertex in \(V_2\), then \(\left(V_1\cup V_2, E_1\cup E_2\cup \{e\}\right)\) is a tree.

5

  1. Prove that any tree with at least two vertices has at least two vertices of degree 1.

  2. Prove that if a tree has \(n\) vertices, \(n \geq 4\), and is not a path graph, \(P_n\), then it has at least three vertices of degree 1.

Answer