Discrete Mathematics for Computer Science

338 CHAPTER 6 Graph Theory

only difference is in the second position (1 and 0). An integer's binary representation can

be found by writing the number as a sum of powers of 2 and then using the coefficients of

this expansion as the binary representation. For example,

61 = I1.2'5+ 1.24 + 1. -2' + 1.22+ 0.-2' + 1.-2'°= 1111012

Example 3. Draw Q2 with the four vertices labeled 00, 01, 10, and 11.

Solution. 00 01

10 11

Obviously an architecture with only four nodes is pretty simple. Hypercubes can

also be used in much larger examples. To make sure you understand how the graphs are

formed, the next example shows Q3. Other properties of hypercubes will be explored in

the exercises.

Example 4. Draw a graph with eight vertices, labeled with the elements of {000, 001,

010, 011, 100, 101, 110, 111 }, the edges of which correspond to the edges of Q3.

Solution. 000 010

100 --- ----- 110

001 Oil

101 111 U

The picture shown in Example 4 should appear to be a "cube." In Exercise 11 of

Section 6.6, you can see how well you can represent Q4 as a "cube."

The Handshaking Problem

A university holds a reception for graduates of the past five years. During the course of

the reception, each attendee shakes hands numerous times. What, if anything, can be said

about the number of times that hands are shaken? For example, can each person shake a

different number of hands?

To find a model, we put this problem in the context of graph theory. We model this

problem with the graph G = (V, E), where

V = {people at the reunion)

E = {(u, v) u, v E Vand u and v shake hands during the reception)

A typical example of such a graph is shown in Figure 6.8. In this graph, there is a

pair of vertices that have the same degree. This means that this pair of people-Sue and

Phil-shook the same number of hands. Is it an accident that a pair of vertices of the graph