ads What Is a Tree?

Section 10.1 What Is a Tree?

Subsection 10.1.1 Definition

What distinguishes trees from other types of connected 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.

🔗

Definition 10.1.1. Cycle.

🔗

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 having at least one pair of vertices connected with two or more edges from consideration as trees.

🔗

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

🔗

Definition 10.1.2. Tree.

🔗

An undirected graph is a tree if it is connected and contains no cycles.

Example 10.1.3. Some trees and non-trees.

Figure 10.1.4. Some trees and some non-trees

Graphs i, ii and iii in Figure 10.1.4 are all trees, while graphs iv, v, and vi are not trees.
A $K_{2}$ is a tree. However, if $n \geq 3,$ a $K_{n}$ is not a tree.
In a loose sense, a botanical tree is a mathematical tree. There are usually no cycles in the branch structure of a botanical tree.
The structures of some chemical compounds are modeled by a tree. For example, butane Figure 10.1.5 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 Figure 10.1.6. There are some compounds whose graphs are not trees. One example is benzene Figure 10.1.7.

Structure of Butane — Figure 10.1.5. Butane

Structure of Isobutane — Figure 10.1.6. Isobutane

Structure of Benzene — Figure 10.1.7. Benzene

🔗

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

🔗

Definition 10.1.8. Forest.

🔗

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

Example 10.1.9. A 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.

🔗

Subsection 10.1.2 Conditions for a Graph to be a Tree

🔗

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.

🔗

Lemma 10.1.10.

🔗

Let

G = (V, E)

be an undirected graph with no self-loops, and let

v_{a}, v_{b} \in V .

If two different simple paths exist between

v_{a}

and

v_{b},

then there exists a cycle in

G .

Proof.

Let

p_{1} = (e_{1}, e_{2}, \dots, e_{m})

and

p_{2} = (f_{1}, f_{2}, \dots, f_{n})

be two different simple paths from

v_{a}

v_{b} .

The first step we will take is to delete from

p_{1}

and

p_{2}

the initial edges that are identical. That is, if

e_{1} = f_{1},

e_{2} = f_{2}, \dots,

e_{j} = f_{j},

and

e_{j + 1} \neq f_{j + 1}

delete the first

j

edges of both paths. Once this is done, both paths start at the same vertex, call it

v_{c},

and both still end at

v_{b} .

Now we construct a cycle by starting at

v_{c}

and following what is left of

p_{1}

until we first meet what is left of

p_{2} .

If this first meeting occurs at vertex

v_{d},

then the remainder of the cycle is completed by following the portion of the reverse of

p_{2}

that starts at

v_{d}

and ends at

v_{c} .

🔗

Theorem 10.1.11. Equivalent Conditions for a Graph to be a Tree.

🔗

Let

G = (V, E)

be an undirected graph with no self-loops and

| V | = n .

The following are all equivalent:

🔗

$G$ is a tree.
For each pair of distinct vertices in $V,$ there exists a unique simple path between them.
$G$ is connected, and if $e \in E,$ then $(V, E - {e})$ is disconnected.
$G$ contains no cycles, but by adding one edge, you create a cycle.
$G$ is connected and $| E | = n - 1 .$

Proof.

Proof Strategy. Most of this theorem can be proven by proving the following chain of implications:

(1) \Rightarrow (2),

(2) \Rightarrow (3),

(3) \Rightarrow (4),

and

(4) \Rightarrow (1) .

Once these implications have been demonstrated, the transitive closure of

\Rightarrow

1, 2, 3, 4

establishes the equivalence of the first four conditions. The proof that Statement 5 is equivalent to the first four can be done by induction, which we will leave to the reader.

(1) \Rightarrow (2)

(Indirect). Assume that

G

is a tree and that there exists a pair of vertices between which there is either no path or there are at least two distinct paths. Both of these possibilities contradict the premise that

G

is a tree. If no path exists,

G

is disconnected, and if two paths exist, a cycle can be obtained by Theorem 10.1.11.

(2) \Rightarrow (3) .

We now use Statement 2 as a premise. Since each pair of vertices in

V

are connected by exactly one path,

G

is connected. Now if we select any edge

e

E,

it connects two vertices,

v_{1}

and

v_{2} .

By (2), there is no simple path connecting

v_{1}

v_{2}

other than

e .

Therefore, no path at all can exist between

v_{1}

and

v_{2}

(V, E - {e}) .

Hence

(V, E - {e})

is disconnected.

(3) \Rightarrow (4) .

Now we will assume that Statement 3 is true. We must show that

G

has no cycles and that adding an edge to

G

creates a cycle. We will use an indirect proof for this part. Since (4) is a conjunction, by DeMorgan’s Law its negation is a disjunction and we must consider two cases. First, suppose that

G

has a cycle. Then the deletion of any edge in the cycle keeps the graph connected, which contradicts (3). The second case is that the addition of an edge to

G

does not create a cycle. Then there are two distinct paths between the vertices that the new edge connects. By Lemma 10.1.10, a cycle can then be created, which is a contradiction.

(4) \Rightarrow (1)

Assume that

G

contains no cycles and that the addition of an edge creates a cycle. All that we need to prove to verify that

G

is a tree is that

G

is connected. If it is not connected, then select any two vertices that are not connected. If we add an edge to connect them, the fact that a cycle is created implies that a second path between the two vertices can be found which is in the original graph, which is a contradiction.

🔗

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.

🔗

Exercises 10.1.3 Exercises

🔗

1.

🔗

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

🔗

$V_{a} = {right, left}$
$V_{b} = {+, -, 0}$
$V_{c} = {north, south, east, west} .$

Answer.

The number of trees are: (a) 1, (b) 3, and (c) 16. The trees that connect

V_{c}

are:

Solution to exercise 10-1-1 — Figure 10.1.12.

🔗

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

| E | = | V | - 1 .

Hint.

Use induction on

| E | .

🔗

4.

🔗

Suppose a forest consists of

m

trees and

v

vertices. What are the possible values of

m

and how many edges does the forest have?

🔗

5.

🔗

Prove that any tree with at least two vertices has at least two vertices of degree 1.
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.

Solution.

Assume that $(V, E)$ is a tree with $| V | \geq 2,$ and all but possibly one vertex in $V$ has degree two or more.

$\begin{aligned} 2 | E | = \sum_{v \in V} \deg (v) \geq 2 | V | - 1 & \Rightarrow | E | \geq | V | - \frac{1}{2} \\ \Rightarrow | E | \geq | V | \\ \Rightarrow (V, E) is not a tree. \end{aligned}$
The proof of this part is similar to part (a). If we assume that there are less than three vertices of degree three, we can still infer $2 | E | \geq 2 | V | - 1$ using the fact that a non-chain tree has at least one vertex of degree three or more.

🔗

6.

🔗

Prove that the center of any tree can have no more than two vertices.

🔗

7.

🔗

Let

(d_{1}, d_{2}, \dots, d_{j}, d_{j + 1}, \dots, d_{n})

be the degree sequence of a tree with

d_{j} \geq 3

and

d_{j + 1} < 3 .

Prove that the number of edges in the tree is

\begin{matrix} (✶) & 2 + \sum_{k = 1}^{j} (d_{k} - 2) . \end{matrix}

Solution.

We can prove this by induction for trees with

n

vertices,

n \geq 2 .

The basis is clearly true since the only tree with two vertices is a

K_{2} .

Now assume that (✶) is true for some

n

greater than or equal to two and consider a tree

T

with

n + 1

vertices. We proceed by removing a leaf from

T .

If there exists a leaf connected to a vertex of degree two, we select one such leaf. The resulting tree satisfies (✶) for the number of leaves; and adding the removed leaf neither changes the number of leaves nor the value of (✶). If all interior vertices have degree three or more remove any leaf from

T .

Again, the number of leaves in the resulting tree is (✶), but this time when we put the removed leaf back on the tree the number of leaves will increase by one, but the value of (✶) will increase by one to match it

You have attempted of activities on this page.

Prev Top Next