Discrete Mathematics for Computer Science

Trees 373

4. T is acyclic and the addition of any edge joining two nonadjacent vertices creates a
   cycle.

Proof.

(1 =. 2) The proof is an induction on n, the number of vertices in T. Let no = 1 and

T = {n e N : all trees on n vertices are connected and m = n - 1}.

(Base step) If n = 1, then the only tree to consider has one vertex and zero edges, so the

result is true for n = 1.

(Inductive step) Now, let n > no. Show that if n E T, then n + 1 E T. Let T be a con-

nected and acyclic graph with n + 1 vertices. Since T is connected, we only have to prove

thatm = n - 1.

Choose a path W in T of maximum length, and let v be an endpoint of W. Vertex v has

degree 1 in T, because W is a maximum length path and T is acyclic. Form the subgraph

T 1 of T consisting of the vertices of T, except for v, and the edges of T, except for the

edge incident with v. T 1 is connected and acyclic and contains n vertices. By induction, T1

contains n - 1 edges. Therefore, T contains n edges.

By the Principle of Mathematical Induction, T = {n E N : n > 1}.

(2 = 3) Suppose T is connected and m = n - 1. We must prove that T is acyclic and

m = n - 1. Since it is given that m = n - 1, it only remains to prove that T is acyclic.

Assume T has a cycle of length c, where c < n. There are c vertices and c edges in the

cycle. If c = n, then m > n, which is a contradiction. For c < n, each of the n - c vertices

not on the cycle is incident to an edge on a shortest path from that vertex to a vertex of the

cycle. Each of these edges is different. Therefore, T contains

m >c+n-c=n

edges, which is a contradiction.

(3 =ý 4) Assume T is acyclic and m = n - 1, and prove that the addition of an edge

joining two nonadjacent vertices creates a cycle.
Since T is acyclic, every component of T must be a tree. Suppose T had k >^1
components. Each component has one more vertex than edge, so n = m + k. However,

n - m = 1, so k = l and T is connected.

Let u and v be any two nonadjacent vertices in T. Since T is connected, there is a

path from u to v. When the edge (u, v) is added to T, a cycle is formed since there are two

distinct paths from u to v in T.

(4 =, 1) Suppose T is acyclic and the addition of any edge joining two nonadjacent
vertices creates a cycle. The proof will be completed by showing that T is connected, since
it is given that T is acyclic.
Suppose T is not connected. T must have at least two connected components. Let u
be a vertex in one component and v be a vertex in a different component. Adding the edge
(u, v) to T does not form a cycle, which is a contradiction. Therefore, T is connected. a

When we study a special class of trees used to represent family trees and various sets
with order relations, we will use the following characterization of trees. In this theorem,
we use only the original definition of a tree in the proof.