➔ A vertex of degree zero is called isolated vertex.
➔ 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.
➔ A pendant vertex is adjacent to exactly one other vertex.
➔ Vertex d in graph G in Example 1 is pendant.
What does the degree of a vertex in a niche overlap graph represent? Which vertices in
this graph are pendant and which are isolated? Use the niche overlap graph shown in
Figure 11 to interpret your answers.
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 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 s
even.
★ Furthermore, the sum of the two terms on the right-hand side 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.
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.
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:
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.
Theorem 3
Let G = (V ,E) be a graph with directed edges. Then
Some special simple Graphs
Complete Graphs
A complete graph on n vertices, denoted by , is a simple graph that contains
exactly one edge between each pair of distinct vertices.
The graphs , for n = 1, 2, 3, 4, 5, 6, are displayed in Figure 3.
A simple graph for which there is at least one pair of distinct vertex not connected
by an edge is called noncomplete.
Cycles
Wheels
n-Cubes
