Discrete Mathematics for Computer Science

372 CHAPTER 6 Graph Theory

n=1 n=2 n=3 n=4 n=5

Figure 6.34 Trees with five or fewer vertices.

6.10.2 Characterization of Trees

Because trees have been "discovered" in so many different contexts, such as mathematics,

chemistry, and electrical engineering, several seemingly different definitions of trees have

been given. The next theorem shows that a number of these definitions are equivalent.

To prove that each of the statements in this theorem describes the same objects, we

must prove that each pair of properties is equivalent. For two properties-say, A and B-

we would do this by proving that property A implies property B and then that property B

implies property A. In the next theorem, we want to prove that four different properties are

equivalent. To prove each pair to be equivalent as above would require 12 proofs. We can,

however, reduce the number of proofs required by using the fact that if property A implies

property B and property B implies property C, then property A implies property C. This

makes a direct proof that property A implies property C unnecessary. To show that n prop-

erties are equivalent, we form a circle of implications-that is, property 1 implies property

2, property 2 implies property (^3) ... , property n implies property 1. Now, for example, to
complete a proof that property i implies property j for any i and j, we simply start at the
implication that property i implies property i + 1 and follow the circle of implications until
the conclusion is property j. Such a sequence of implications and the transitive property
of implication lead to the desired conclusion. More formally, what we observe is that the
formula
(PI +-+ P2) A (pl '+ P3) A (pl <-' P4) A (P2 <+- P3) A (P2 <+- P4) A (P3 <-+ P4)
is logically equivalent to the formula

(PI -' P2) A (P2 -- P3) A (P3 - P4) A (P4 -- P0).

The proof of Theorem 1 uses a circle of implications. In Theorem 1, the number of

proofs is reduced to four from 12 by using this proof technique.

Theorem 1. (Tree Characterization) Let T be a graph with n vertices and m edges.

The following statements are equivalent:

1. T is a tree.


2. T is connected and m = n - 1.


3. T is acyclic andm = n - 1.