Page 674 - Discrete Mathematics and Its Applications

10.2 Graph Terminology and Special Types of Graphs 653

ecosystem. Finally, the vertex representing a species is isolated if this species does not compete
with any other species in the ecosystem.
For instance, the degree of the vertex representing the squirrel in the niche overlap graph
in Figure 11 in Section 10.1 is four, because the squirrel competes with four other species: the
crow, the opossum, the raccoon, and the woodpecker. In this niche overlap graph, the mouse is
the only species represented by a pendant vertex, because the mouse competes only with the
shrew and all other species compete with at least two other species. There are no isolated vertices
in the graph in this niche overlap graph because every species in this ecosystem competes with
at least one other species. ▲

What do we get when we add the degrees of all the vertices of a graph G = (V, E)? Each
edge contributes two to the sum of the degrees of the vertices because an edge is incident with
exactly two (possibly equal) vertices. This means that the sum of the degrees of the vertices
is twice the number of edges. We have the result in Theorem 1, which is sometimes called
the handshaking theorem (and is also often known as the handshaking lemma), because of the
analogy between an edge having two endpoints and a handshake involving two hands.

THEOREM 1 THE HANDSHAKING THEOREM Let G = (V, E) be an undirected graph with m
edges. Then

2m = deg(v).
v∈V

(Note that this applies even if multiple edges and loops are present.)

EXAMPLE 3 How many edges are there in a graph with 10 vertices each of degree six?

Solution: Because the sum of the degrees of the vertices is 6 · 10 = 60, it follows that 2m = 60
where m is the number of edges. Therefore, m = 30. ▲

Theorem 1 shows that the sum of the degrees of the vertices of an undirected graph is even.
This simple fact has many consequences, one of which is given as Theorem 2.

THEOREM 2 An undirected graph has an even number of vertices of odd degree.

Proof: Let V 1 and V 2 be the set of vertices of even degree and the set of vertices of odd degree,
respectively, in an undirected graph G = (V, E) with m edges. Then

2m = deg(v) = deg(v) + deg(v).
v∈V v∈V 1 v∈V 2

Because deg(v) is even for v ∈ V 1 , the first term in the right-hand side of the last equality is
even. Furthermore, the sum of the two terms on the right-hand side of the last equality is even,
because this sum is 2m. Hence, the second term in the sum is also even. Because all the terms in
this sum are odd, there must be an even number of such terms. Thus, there are an even number
of vertices of odd degree.

Terminology for graphs with directed edges reflects the fact that edges in directed graphs
have directions.