Page 673 - Discrete Mathematics and Its Applications

652 10 / Graphs

We will also find useful terminology describing the set of vertices adjacent to a particular vertex
of a graph.

DEFINITION 2 The set of all neighbors of a vertex v of G = (V, E), denoted by N(v), is called the neigh-
borhood of v.If A is a subset of V , we denote by N(A) the set of all vertices in G that are

adjacent to at least one vertex in A. So, N(A) = v∈A N(v).

To keep track of how many edges are incident to a vertex, we make the following definition.

DEFINITION 3 The degree of a vertex in an undirected graph is the number of edges incident with it, except
that a loop at a vertex contributes twice to the degree of that vertex. The degree of the
vertex v is denoted by deg(v).

EXAMPLE 1 What are the degrees and what are the neighborhoods of the vertices in the graphs G and H
displayed in Figure 1?

Solution: In G,deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d ) = 1, deg(e) = 3, and
deg(g) = 0. The neighborhoods of these vertices are N(a) ={b, f }, N(b) ={a, c, e, f },
N(c) ={b, d, e, f }, N(d) ={c}, N(e) ={b, c, f }, N(f ) ={a, b, c, e}, and N(g) =∅.In
H,deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, and deg(d ) = 5. The neighborhoods of
these vertices are N(a) ={b, d, e}, N(b) ={a, b, c, d, e}, N(c) ={b}, N(d) ={a, b, e}, and
N(e) ={a, b, d}. ▲

b c d a b c

a f e g e d
G H

FIGURE 1 The Undirected Graphs G and H.

A vertex of degree zero is called isolated. It follows that an isolated vertex is not adjacent
to any vertex. Vertex g in graph G in Example 1 is isolated. A vertex is pendant if and only
if it has degree one. Consequently, a pendant vertex is adjacent to exactly one other vertex.
Vertex d in graph G in Example 1 is pendant.
Examining the degrees of vertices in a graph model can provide useful information about
the model, as Example 2 shows.
EXAMPLE 2 What does the degree of a vertex in a niche overlap graph (introduced in Example 11 in Sec-
tion 10.1) represent? Which vertices in this graph are pendant and which are isolated? Use the
niche overlap graph shown in Figure 11 of Section 10.1 to interpret your answers.

Solution: There is an edge between two vertices in a niche overlap graph if and only if the two
species represented by these vertices compete. Hence, the degree of a vertex in a niche overlap
graph is the number of species in the ecosystem that compete with the species represented by
this vertex. A vertex is pendant if the species competes with exactly one other species in the