Page 675 - Discrete Mathematics and Its Applications

654 10 / Graphs

DEFINITION 4 When (u, v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v
is said to be adjacent from u. The vertex u is called the initial vertex of (u, v), and v is called
the terminal or end vertex of (u, v). The initial vertex and terminal vertex of a loop are the
same.

Because the edges in graphs with directed edges are ordered pairs, the definition of the degree
of a vertex can be refined to reflect the number of edges with this vertex as the initial vertex and
as the terminal vertex.

−
DEFINITION 5 In a graph with directed edges the in-degree of a vertex v, denoted by deg (v), is the number
+
of edges with v as their terminal vertex. The out-degree of v, denoted by deg (v), is the
number of edges with v as their initial vertex. (Note that a loop at a vertex contributes 1 to
both the in-degree and the out-degree of this vertex.)

EXAMPLE 4 Find the in-degree and out-degree of each vertex in the graph G with directed edges shown in
Figure 2.

a c
b

e d f
G
FIGURE 2 The Directed Graph G.

−
−
−
−
Solution: The in-degrees in G are deg (a) = 2, deg (b) = 2, deg (c) = 3, deg (d) = 2,
−
+
+
+
−
deg (e) = 3, and deg (f ) = 0. The out-degrees are deg (a) = 4, deg (b) = 1, deg (c) = 2,
+
deg (d) = 2, deg (e) = 3, and deg (f ) = 0. ▲
+
+
Because each edge has an initial vertex and a terminal vertex, the sum of the in-degrees and
the sum of the out-degrees of all vertices in a graph with directed edges are the same. Both of
these sums are the number of edges in the graph. This result is stated as Theorem 3.
THEOREM 3 Let G = (V, E) be a graph with directed edges. Then

− +
deg (v) = deg (v) =|E|.
v∈V v∈V
There are many properties of a graph with directed edges that do not depend on the direction
of its edges. Consequently, it is often useful to ignore these directions. The undirected graph that
results from ignoring directions of edges is called the underlying undirected graph. A graph
with directed edges and its underlying undirected graph have the same number of edges.

Some Special Simple Graphs

We will now introduce several classes of simple graphs. These graphs are often used as examples
and arise in many applications.