CC 141

Discrete Structures
Department of Computer Science
School of Systems and Technology

University of Management and Technology

Lahore, Pakistan
 Chapter 10

Graph Theory
 INTRODUCTION
• Graph theory plays an important role in several areas of
computer science such as:

• Switching Theory and Logical Design

• Artificial Intelligence
• Formal Languages
• Computer Graphics
• Operating Systems
• Compiler Writing
• Information Organization and Retrieval.
 Graph … Examples
Social Network Graph
Individuals and their friends refer to social networks and their
arrangement reflects a graph. Individuals in social networks and
relationships among different individuals make up social network
graph.

Social Network:
 Graph … Examples
Road Network Graph
Cities may be referred as vertices and roads joining them are the edges
of the graph.

Road Network Example

 Graph … More Examples
Car Navigation System

Artificial Intelligence

Graph of Web

Professional Network Graph

Course Pre-reqs Graph

Job Execution Graph

Operating Systems

Airline Routes

Many more….
 GRAPH
• A graph is a non-empty set of points called vertices and
A set of line segments joining pairs of vertices called edges.

• Formally, a graph G = (V, E) consists of two finite sets:

• A set V = V(G) of vertices (or points or nodes)

• A set E = E(G) of edges;

where each edge corresponds to a pair of vertices.

 EXAMPLE
• We have five vertices labeled by v1, v2, v3, v4, v5 .
• We have edges e1, e2, e3, e4, e5, e6 .
• e1 edge is for vertices v1 and v2 . v1 e1 v2
• e2 and e3 end points are v1 and v4.
• e4 has end points v2 and v4 . e4
• e5 has end points v2 and v3 . e3 e2 e5 v5
• e6 is a loop .
v3
v4 e6
 SOME TERMINOLOGY
v1 e1 v2
e4
e3 e2 e5 v5

v3
v4 e6

• An edge connects either one or two vertices called its endpoints

(edge e1 connects vertices v1 and v2 described as {v1, v2} i.e v1 and v2
are the endpoints of an edge e1).
 SOME TERMINOLOGY
• An edge with just one endpoint is called a loop. Thus a loop is an edge that
connects a vertex to itself (e.g., edge e6 ).

• Two vertices that are connected by an edge are called adjacent; and a vertex
that is an endpoint of a loop is said to be adjacent to itself.

• An edge is said to be incident on each of it endpoints(i.e. e1 is incident on v1

and v2 ).

• A vertex on which no edges are incident is called isolated (e.g., v5)

• Two distinct edges with the same set of end points are said to be parallel
(i.e. e2 & e3).
 EXAMPLE
• Define the following graph formally by specifying its vertex set, its edge
set, and a table giving the edge endpoint function.
e1
v1 v2

e2 v4
v3
e3
Solution:

Vertex Set = {v1, v2, v3, v4} Edge Endpoint

e1 {v1, v2}
Edge Set = {e1, e2, e3}
e2 {v1, v3}
e3 {v3}
Edge - endpoint function is:
 EXAMPLE
• For the graph shown below:

• Find all edges that are incident on v1;

• Find all vertices that are adjacent to v3;
• Find all loops;
• Find all parallel edges; e3
• Find all isolated vertices; e1
e2 v2
v1 e6
e4
e7
e5 v3
v5
v4
 SOLUTION
• Find all edges that are incident on v1?
• v1 is incident with edges e1, e2 and e7

• Find all vertices that are adjacent to v3?

• vertices adjacent to v3 are v1 and v2

• Find all loops?

• Loops are e1 and e3

• Find all parallel edges?

• Only edges e4 and e5 are parallel

• Find all isolated vertices?

• The only isolated vertex is v4 in this Graph.
 EXERCISE
• Draw picture of Graph H having vertex set {v1, v2, v3, v4, v5} and
edge set {e1, e2, e3, e4} with edge endpoint function:
Edge Endpoint
e1 {v1}
e2 {v2, v3}
e3 {v2, v3}
e4 {v1, v5}

Solution:
Given V(H) = {v1, v2, v3, v4, v5} and
E(H) = {e1, e2, e3, e4}
with edge endpoint function
 SIMPLE GRAPH
A simple graph is a graph that does not have any loop or parallel edges.
Example:
v1 e1 v2

e2 e3 v5
e4

v4 v3

These are simple graphs, each graph has 5 vertices and 4 edges.
V(G) = {v1, v2, v3, v4, v5} & E(G) = {e1, e2, e3, e4}
 EXERCISE
Draw all simple graphs with the four vertices {u, v, w, x} and two edges, one of
which is {u, v}.
Solution:
We are given four vertices {u, v, w, x} and one edge is {u, v}.
Since we are interested in simple graph so we cannot take {u, v} again.
• There are C(4,2) = 6 ways of choosing two vertices from 4 vertices.
• These edges may be listed as:
{u, v}, {u, w}, {u, x}, {v, w}, {v, x}, {w, x}
• One edge of the graph is specified to be {u, v}, so any of the remaining five from
this list may be chosen to be the second edge.
• This required graphs are:
1. 2. 3.
u v u v u v

w x w x
w x

4. 5.
u v u v

w x w x
 DEGREE OF A VERTEX

• Let G be a graph and v a vertex of G. The degree of v, denoted

deg(v), equals the number of edges that are incident on v,
with an edge that is a loop counted twice.

• The total degree of G is the sum of the degrees of all the

vertices of G.

• The degree of a loop is counted twice.

 EXAMPLE
• Find the degree of every vetex of the graph and the total degree of the graph
shown v2
. v1
• deg (v1) = 0, since v1 is isolated vertex.
• deg (v2) = 2, since v2 is incident on e1 and e2.
e1 e2
• deg (v3) = 4, since v3 is incident on e1,e2 and the loop e3.
• Total degree of G = deg(v1) + deg(v2) + deg(v3)
v3
=0+2+4=6
NOTE
e3
The total degree of G, which is 6, equals twice the number of edges of G,
which is 3.

This is always the case the total degree of graph is always twice the number of edges in that graph.
This is actually the theorem called Handshaking Theorem.
 THE HANDSHAKING THEOREM
• If G is any graph, then the sum of the degrees of all the vertices of G
equals twice the number of edges of G.

• Specifically, if the vertices of G are v1, v2, …, vn, where n is a positive

integer, then

• The total degree of

G = deg(v1) + deg(v2) + … + deg(vn)
= 2 . (the number of edges of G)
Corollary
• The total degree of G is an even number
 EXERCISE
• Draw a graph with the specified properties or explain why no
such graph exists.

(i) Graph with four vertices of degrees 1, 2, 3 and 3

(ii) Graph with four vertices of degrees 1, 2, 3 and 4
(iii) Simple graph with four vertices of degrees 1, 2, 3 and
4.
 Solution
(i) Graph with four vertices of degrees 1, 2, 3 and 3
Total degree of graph = 1 + 2 + 3 + 3
= 9 an odd integer
Hence by Hand-Shaking Theorem, first graph is not possible.
1.
a b

(ii) Graph with four vertices of degrees 1, 2, 3 and 4

Total degree of graph = 1 + 2 + 3 + 4 d c
= 10 an even integer
• The vertices a, b, c, d have degrees 1, 2, 3, and 4 respectively 2.
a

(i.e. graph exists). b

deg(a) = 1 deg(b) = 2
c
deg(c) = 3 deg(d) = 4
d
(iii) Simple graph with four vertices of degrees 1, 2, 3 and 4.

• Suppose there was a simple graph with four vertices of degrees 1, 2, 3, and
4. Then the vertex of degree 4 would have to be connected by edges to four
distinct vertices other than itself because of the assumption that the graph
is simple (and hence has no loop or parallel edges.) This contradicts the
assumption that the graph has four vertices in total.

• Hence there is no simple graph with four vertices of degrees 1, 2, 3, and 4,

so simple graph is not possible in this case.
 EXERCISE
• Suppose a graph has vertices of degrees 1, 1, 4, 4 and 6. How
many edges does the graph have?

• SOLUTION:
The total degree of graph = 1 + 1 + 4 + 4 + 6
= 16
16
8
 Number of edges of graph = 2
 COMPLETE GRAPH
• A complete graph on “n” vertices is a simple graph in which each
vertex is connected to every other vertex and is denoted by Kn (Kn
means that there are n vertices).
v1
v1 v2 v1
K1
K2
v2 v3 v2
v1
v4 v1 v5

v2 v3 v3 v4
K5
K4
 REGULAR GRAPH
• A graph G is regular graph of degree k or k-regular if every vertex of
G has degree k.
• In other words, a graph is regular if every vertex has the same
degree.
• Following are some regular graphs.

(i) 0-regular (ii) 1-regular

(iii) 2-regular
 EXERCISE
Draw two 3-regular graphs with six vertices.

SOLUTION:
a
a b
f b
f c

e c

e d d
 BIPARTITE GRAPH
• A bipartite graph G is a simple graph whose vertex set can be
partitioned into two mutually disjoint non empty subsets A
and B such that the vertices in A may be connected to vertices
in B, but no vertices in A are connected to vertices in A and no
vertices in B are connected to vertices in B.

v1 v2 v3 A B
A
v1 v4
v2 v5
v3 v6
B
v4 v5
MATRIX REPRESENTATIONS OF GRAPHS
• To store graph in computer with pictorial representation is
not possible rather you will store the graph with matrix
representation.

• It is difficult to analyze a big complex graph with hundreds of

vertices and thousands of edges, but in matrix form you can
analyze big graph better.
 MATRIX
• An m  n matrix A over a set S is a rectangular array of elements of S
arranged into m rows and n columns:
 a11 a12  a1 j  a1n 
a a  a  a 
 21 22 2j 2n 

    
A  
 ai1 ai 2  aij  ain 
    
 
 am1 am 2  amj  amn 


jth column of A
 ADJACENCY MATRIX OF A GRAPH
Let G be a graph with ordered vertices v1, v2,..., vn. The adjacency
matrix of G is the matrix A = [aij] over the set of non-negative
integers such that

aij = the number of edges connecting vi and vj

for all i, j = 1, 2, …, n.
OR
The adjancy matrix say A= [aij] is also defined as
1 if {vi , v j } is an edge of G
aij 
0 otherwise
 EXAMPLE
• A graph with it’s adjacency matrix is shown.

• Clearly graph has four vertices. It means that the corresponding

square matrix will be order 4 x 4.
 EXERCISE
Find a graph that have the following adjacency matrix.
 0 2 0
 2 1 0
 
 0 0 1 
Solution
Its order is 3 x 3, it means its corresponding graph has three vertices.
• Let the three vertices of the graph be named v1, v2 and v3
v1 v2 v3 v2 v1
 0 2 0
 2 1 0
  v3
 0 0 1
 DIRECTED GRAPH
• A directed graph or digraph, consists of two finite sets: a set V(G) of
vertices and a set D(G) of directed edges,

• where each edge is associated with an ordered pair of vertices called

its end points.

• If edge e is associated with the pair (v, w) of vertices, then e is said to

be the directed edge from v to w and is represented by drawing an
arrow from v to w.
EXAMPLE OF DIGRAPGH
v2
e1
e3 e4
v1
e
e5 2
v4
e6 v3
ADJACENCY MATRIX OF A DIRECTED
GRAPH
• Let G be a graph with ordered vertices
v1, v2, …, vn.

• The adjacency matrix of G is the matrix A = [aij] over the set of

non-negative integers such that

aij = the number of arrows from vi to vj

for all i, j = 1, 2, …, n.
 EXAMPLE
• A directed graph with its adjacency matrix is shown
v2v2
v1v1 v2v2 v3v3 v4v4
e1e1 v1v1 11 00 11 00

e4e4
v1v1
e3e3 v2v2 0
0 
00 11 00
ee AA  
e5e5 2 2 v3v3 11 
00 00 11
v4v4  
v3v3 v4v4 00 00 11 00

e6e6

Adjacency matrix
 EXERCISE
• Find directed graph that has the adjacency matrix
1 0 1 2
0 0 1 0 

0 2 1 1
 
0 1 1 0

• The order of matrix is 4 x 4, it means it has 4 vertices.

 SOLUTION
• The 4  4 adjacency matrix shows that the graph has 4 vertices say v1, v2,
v3 and v4 labeled across the top and down the left side of the matrix.
v1 v2 v3 v4 A corresponding directed graph is
v1  1 0 1 2
v1 v2
v2  0 0 1 0 
A 
v3  0 2 1 1
 
v4  0 1 1 0
v3
v4

• It means that a loop exists from v1 and v3 , two arrows go from v1 to v4

and two from v3 and v2 and one arrow go from v1 to v3 , v2 to v3 , v3 to v4, v4
to v2 and v3.
Graph Adjacency Matrix Representation
Draw adjacency matrix for given directed graph.
Solution:
The Given Graph

Graph A B C D E
G
Graph G
A 0 1 1 0 0
B 0 0 0 1 0
C 0 0 0 0 1
D 0 0 0 0 1
E 0 0 0 0 0
The
Graph Adjacency Matrix … Exercise
Draw adjacency matrix for given graph G:

Graph G
Graph Adjacency Matrix Representation
Draw the adjacency matrix of given graph G.

Solution Pseudo Graph

G
Graph G A B C D
A 1 1 1 2
B 2 0 0 0
C 0 0 1 0
D 0 0 0 0
Graph Adjacency Matrix
Representation …
Draw the graph with given adjacency matrix:
Graph Adjacency Matrix Representation …
Draw the adjacency matrix for the given graph.
INCIDENCE MATRIX OF A SIMPLE GRAPH
Let G be a graph with vertices v1, v2, …, vn and edges e1, e2, …, en.

The incidence matrix of G is the matrix M = [mij] of size n  m

defined by:

1 if the vertex vi is incident on the edge e j

mij 
0 otherwise
 EXERCISE

• A graph with its incidence matrix is shown.

 REMARK
• In the incidence matrix:

• Parallel edges are represented by columns with identical entries

(in this matrix e4 & e5 are parallel edges).

• Loops are represented using a column with exactly one entry

equal to 1, corresponding to the vertex that is incident with this
loop and other zeros (here e2 is only a loop).
INCIDENCE MATRIX OF A DIRECTED GRAPH
Let G be a graph with vertices v1, v2, …, vn and edges e1, e2, …, en.

The incidence matrix of G is the matrix M = [mij] of size n  m

defined by:
 In Degree, Out Degree
In Degree:
Number of edges pointing into a vertex is called its in degree.
In Degree of vertex A is 2
Out Degree:
Number of edges going out of a vertex is called its out degree.
Out Degree of vertex A is 4
In Degree, Out Degree
In Degree:
Number of edges pointing into a vertex is called its in degree
In Degree of vertex A is 2
Out Degree:
Number of edges going out of a vertex is called its out degree
Out Degree of vertex A is 4

Note: Sum of degrees for all nodes of a graph is always

even
Degree, In Degree, Out Degree … Example
Calculate:
i. Degree of K
ii. In degree of all vertices of K
iii. Out degree of all vertices of K
iv. Degree of sub-graph involving vertices G&H Only

Graph K
Degree, In Degree, Out Degree … Example
If each vertex of an undirected graph has degree k then the
graph is called a regular graph of degree k.

1. How many edges are there in a directed graph of degree 6?

2. How many edges are there in a undirected graph of degree
10?
3. How many edges are there in a undirected graph of degree
N?
 Summary
The topics we covered:
• Graphs
• Terminologies
• Types of Graphs
• Matrix Representation of Graphs
• Directed Graph