Discrete Mathematics for Computer Science

The Handshaking Problem 339

have the same degree? Theorem 1 says that in any graph with at least two vertices, there

are always at least two vertices of the same degree.

Jack

John

Phil Sue

4Bill

Jane Jil

Figure 6.8 Handshaking graph.

Theorem 1. (Handshaking Theorem) Let G be a graph with at least two vertices. At

least two vertices of G have the same degree.

Proof. The proof is by induction on the number of vertices n in a graph. Let no = 2 and

T = {n E N : any graph with n vertices has at least two vertices of the same degree}.

(Base step) For no, the only graphs to consider are the graph consisting of two isolated

vertices and the graph having a single edge. Clearly, the result holds for each of these

graphs. Therefore, the base case no = 2 is true and no E T.

(Inductive step) Let n > no. Show that if n E T, then n + 1 E T. Assuming that any

graph on n vertices with n > 2 has two vertices of the same degree, we must prove that any

graph on n + 1 vertices has two vertices of the same degree. Let G = (V, E) be a graph

with n + 1 vertices where n ± 1 > 3. Clearly, 0 < deg(v) < n for any v E V. If there is an

isolated vertex in G, then by the induction hypothesis, the subgraph of G consisting of all

the vertices but one isolated vertex must have two vertices with the same degree. Adding

an isolated vertex to the subgraph with at least two vertices having the same degree gives

the result for G. If there is no isolated vertex in G, then all the degrees of vertices v E V

satisfy 1 < deg(v) < n. In this case, we have at most n different values for the degrees of

vertices in G. Since G has n + 1 vertices, then by the Pigeon-Hole Principle, at least two

vertices of G have the same degree. Therefore, n + 1 E T.

By the Principle of Mathematical Induction, T = In E N : n > 2}. 0

It was indeed no accident that two people, at least, shook the same number of hands.

The graph shown in Figure 6.8 also has four odd vertices. Is it an accident that there

are an even number of odd vertices? Before proving the theorem that answers this question,

we need to prove a result that will be used in its proof.

Theorem 2. Let G = (V, E) be a graph. Then, ZvEV deg(v) = 2. I E I.

Proof. The sum

E deg(v)

vEV

represents the sum of the degrees of each of the vertices. This sum counts the number of
edges twice, since each edge is incident to two vertices. Therefore,

E deg(v) = 2. I E I

yEV U