For Exercises 3–9, determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more loops. Use your answers to determine the type of...

Graphs Eng.Jehad Aldahdooh
 Introduction To Graphs:

 Definitions:
 A graph G = (V, E) consists of V, a nonempty set of vertices (or nodes) and E, a set of
edges. Each edge has either one or two vertices associated with it, called its end points.
An edge is said to connect its endpoints.
 A directed graph (or digraph) (V, E) consists of a nonempty set of vertices V and a set
of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of
vertices. The directed edge associated with the ordered pair (u, v) is said to start at u
and end at v.

 Exercises

1. Determine whether the graph shown has directed or undirected edges, whether it has multiple
edges, and whether it has one or more loops. Use your answers to determine the type of graph
in Table 1 this graph is.
Solution:
Type Comment
3 Simple graph Undirected edges, no parallel edges or loops
4 multigraph Undirected edges, no loops but a parallel edges
5 Pseudograph Undirected edges, with loops and parallel edges
6 multigraph Undirected edges, no loops but a parallel edges
7 directed graph Directed edges, no parallel edges but loops.
8 directed multigraph Directed edges, parallel edges and loops.
9 directed multigraph Directed edges, parallel edges and loops.
 Graph Terminology
 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 of G. If e is associated with {u, v}, the edge e is
called incident with the vertices u and v. The edge e is also said to connect u and v.
The vertices u and v are called endpoints of an edge associated with {u, v}.
 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).
o A vertex with degree 0 is called isolated.
o A vertex of degree 1 is called pendant.
 THE HANDSHAKING THEOREM Let G = (V, E) be an undirected graph with e
edges. Then
 When (u, v) is an edge of the graph G with...