Discrete Mathematics for Computer Science

Trees 371

H H

H H HH

H H H C H H CC H

H

H C C H H C H H

H C

Methane H c-.H H

Ethane H C H C

H H H1

Butane Isobutane

(a) Cayley's graphs for hydrocarbon compounds

G: T:

(b) Kirchoff's graphs for electrical network

Figure 6.33 Cayley's and Kirchoff's graphs. a. Cayley's graphs for hydrocarbon compounds.

b. Kirchoff's graphs for an electrical network.

6.10.1 Definition of Trees

A good way to deal with a new mathematical structure is to construct examples that satisfy

the definition. You should try this approach with the next definition, in which we will make

use of the term acyclic (see Definition 6 in Section 6.3).

Definition 1. A tree is a connected acyclic graph. A graph in which each connected

component is a tree is called a forest. A vertex of degree one in a tree is called a leaf,

or a terminal vertex. A vertex of degree greater than one in a tree is called an interior

vertex.

For the usual definition of trees, the vertex set may not be empty. Later, a special
application will be facilitated by relaxing this restriction on the definition of a tree.
In Figure 6.34, we see all the trees with fewer than six vertices. Can you deduce a
relationship between the number of vertices and the number of edges in a tree from these
examples?