Discrete Mathematics for Computer Science

340 CHAPTER 6 Graph Theory

We will now use this result to prove another property of graphs that can be interpreted

for the handshaking graph to mean that an even number of people shook an odd number of

hands.

Theorem 3. In any graph, the number of odd vertices is even.

Proof. Let G = (V, E) be a graph. By Theorem 2, we have

E deg(v) = 2. I El

vEV

The next step is to rewrite the left-hand side of the equation as

Sdeg(v) = L deg(v) + • deg(v)

vEV v odd v even

We now have

Z deg(v)+ ÷ deg(v) =2IE

"v odd v even

or

y deg(v) = 2 I EI- deg(v)

"v odd v even

Since the right-hand side of the equation is an even number, the left-hand side of the equa-

tion is an even number. Therefore, an even number of vertices are included in the sum on

the left-hand side, since the sum of an odd number of odd numbers would be odd. 0

Theorem 3 has proved it was no accident that an even number of people shook an odd

number of hands. Although this result was motivated by the handshaking problem, you will

find other important applications for these two theorems in many instances when a graph

models a problem.

W Paths and Cycles

The graph theory notions defined here are important not only because of their application to

describing problems but also because they give important tools to use in problem solving.

For example, the design for the layout of circuits in computer chips can be described in

terms of these notions.

Definition 5. Let G = (V, E) be a graph. A trail in a graph G is a sequence of not

necessarily distinct vertices v1, V2 ..... Vk of G such that (vi, vi+i) G E for 1 < i < k - 1

and the edges are distinct. A trail with k vertices is denoted by Tr(k). If all the vertices in

a trail are distinct, the trail is called a path. The length of a path or a trail is the number of

edges it contains. A path or trail of length zero consists of a single vertex. A path of length

n is denoted by Pn. The distance between two vertices a and b is the length of a shortest

path joining a to b. If no path between a and b exists, then the distance is commonly

defined to be infinity or, in some instances, left undefined.

Although a trail is defined as a sequence of vertices and certain associated edges, we

often display a trail or a path simply as if it were a subgraph with the vertices and edges