Graph Terminology

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.

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


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.