Basic Terminology: First, we give some terminology that describes the vertices and edges of undirected graphs.

DEFINITION 1 Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v.

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 neighborhood 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}.

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 Section 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 ecosystem. Finally, the vertex representing a species is isolated if this species does not compete with any other species in the ecosystem.

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

Then
(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 V1 and V2 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

Because deg(v) is even for v ∈ V1, 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.

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.