GRAPH THEORY
Graphs and Digraphs
SIMPLE GRAPHS
• A graph (undirected graph/simple graph) consists of a finite set of
points, called vertices (nodes), and a set of line segments, called edges,
which join distinct pairs of vertices.
• We denote the graph by G (and H if two graphs are being discussed), the
set of vertices of G by V(G), and the set of edges of G by E(G). A single
element from the set of vertices is called a vertex (vertices is the plural
form of vertex).
• We label the vertices by
lowercase letters. An edge
is then denoted by listing the
vertices that are its endpoints.
• Example: G(V,E) is given as
follows:
SIMPLE GRAPHS: EXERCISE 1
EXERCISE 1: Construct graphs with the following
vertex and edge sets:
a) V(G) = {a,b,c,d}, E(G) = {ab,cd,bd,bc}
b) V(H) = {e,f , g ,h,i,j}, E(H) = {eh,ej,hi,ij,fh,hj}
SIMPLE GRAPH NOTIONS
• If there is an edge joining a pair of vertices, those vertices are said to
be adjacent. Otherwise, they are nonadjacent.
• Example: a and b are adjacent while a and c are nonadjacent vertices.
• The degree of a vertex v is the number of edges linked with v and is
denoted d(v).
• Example: d(a)=
d(c) = , d(e)=
• The degree sequence
of a graph is the list of the
degrees of its vertices in
nonincreasing order.
• Example:
SIMPLE GRAPH NOTIONS: EXERCISES
EXERCISE 2: For the following graph, list V(G),
E(G), the degree of each vertex, and the degree
sequence.
EXERCISE 3: Three graphs have degree sequence
3, 2, 2, 1, 1, 1. Find two of them.
First theorem of graph theory
• Since an edge contributes 1 to the degree of
each of its two endpoints, we have the
following theorem, called the "first theorem of
graph theory.“
• Theorem: In a graph G, the sum of the
degrees of the vertices equals twice the
number of edges .
• Corollary: The sum of the degrees of the
vertices of a graph is an even number.
First theorem: EXERCISES
EXERCISE 4: Why is 5, 3, 3, 2, 1, 1, 1, 1 not the
degree sequence of a graph?
EXERCISE 5: Although 5 + 2 + 1 + 1 + 1 = 10
(which is even), 5, 2, 1, 1, 1 is not the degree
sequence of a graph. Why?
Conclusion:
Multigraphs and Pseudographs
• A multigraph allows more than one edge
between a pair of vertices. Such edges are called
multiple edges.
• A loop is an edge that connects a vertex to itself.
A pseudograph allows loops and multiple edges.
Digraphs
• A directed graph or digraph (for short) consists of a set of vertices and
a set of directed edges called arcs, which join pairs of distinct vertices.
• In a digraph, parallel arcs are a pair of arcs, one directed from vertex a
to vertex b and the other directed from b to a.
• The indegree of a vertex v is the number of arcs directed toward v and
is denoted id(v). The outdegree of v is the number of arcs directed
away from v and is denoted od(v).
• Example: List the arcs in the digraph of G.
• List the indegree and the outdegree of vertex c.
Digraphs: Theorem
• Theorem: In a digraph, the sum of the
indegrees equals the sum of the outdegrees.
• EXERCISE 6: The maximum number of edges in
a graph having n vertices is …
• EXERCISE 7: The maximum number of arcs in a
digraph with n vertices is …
