LECTURE # 39

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
A graph is a nonempty set of points called vertices and a set of line
segments joining pairs of vertices called edges.
Formally, a graph G consists of two finite sets:
(i) A set V=V(G) of vertices (or points or nodes)
(ii) A set E=E(G) of edges; where each edge corresponds to a pair of
vertices. v1 e1 v2

e3 e2 e5
e4 v5

v3
v4
e6
The graph G with
V(G) = {v1, v2, v3, v4, v5} and
1
E(G) = {e1, e2, e3, e4, e5, e6}
 SOME TERMINOLOGY

We are taking the same graph which we take in the previous example to
introduce some terminology.

v1 e1 v2

e3 e2 e5
e4 v5

v3
v4
e6

1. An edge connects either one or two vertices called its endpoints.

(edge e1 connects vertices v1 and v2 described as {v1, v2}).
2. An edge with just one endpoint is called a loop. That is a loop is an
edge that connects a vertex to itself (e.g., edge e6)
3. 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.

4. An edge is said to be incident on each of its endpoints.

5. A vertex on which no edges are incident is called isolated.
(e.g., v5)
6. Two distinct edges with the same set of end points are said to be
parallel. (e2 & e3).

2
 EXAMPLE

Define the following graph formally by specifying its vertex set, its edge
set, and a table giving the edge endpoint function.

v1 e1 v2

e2 v4
v3

e3
SOLUTION
Vertex Set = {v1, v2, v3, v4}
Edge Set = {e1, e2, e3}
Edge - endpoint function:
Edge Endpoint
e1 {v1, v2}
e2 {v1, v3}
e3 {v3}

EXAMPLE
For the graph shown
e1 e3

e2 v2
v1 e6
e4 e7

e5 v3

v5
3
v4
(i) find all edges that are incident on v1.
(ii) find all vertices that are adjacent to v3.
(iii) find all loops.
(iv) find all parallel edges.
(v) find all isolated vertices.
e1 e3

e2 v2
v1 e6
e4 e7

e5 v3

v5

v4

SOLUTION
(i) Since we know that edges incidence on a vertices v are those e which
has v as an end point so from above diagram it is quite clear that
edges incident on v1 are e1, e2 and e7
(ii) Remember that we say that two vertices are adjacent if there is an
edge between them thus from diagram we can say vertices adjacent to
v3 are v1 and v2..
(iii) loops are e1 and e3
(iv) Two edges are said to be parallel if they have the same end points.
Hence from diagram it is clear that only edges e4 and e5 are parallel
(v) only isolated vertex is v4
4
 DRAWING PICTURE FOR A GRAPH

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}
First of all we note that there are 5 vertices so we made three dots and label
them as v1, v1, v3, v4, v5 as vertices. Now we will proceed and draw the
graph by noting the edge point function as e1

Since e1 edge has only one end

v2 v1
point it means that there is a loop at the e4
Vertex v1. e2
v5
Then e2 has its end points {v2,v3} so
e3
we made an edge between these
v4
two vertices. v3
Similarly we draw all the edges and find the graph as in front of us.

5
 SIMPLE GRAPH
A simple graph is a graph that does not have any loop or parallel edges.
EXAMPLE
v1 e1 v2

v5
e2 e4
e3

v4 v3
A simple graph H
V(H) = {v1, v2, v3, v4, v5}
E(H) = {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
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:

6
 1. 2.
u v u v

w x
w x

3.
u v

4.
w x 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.

7
 EXAMPLE

v2
For the graph shown . v1
deg (v1) = 0, since no edge is incident on v1.
deg (v2) = 2, since both e1 and e2 are incident on v2.
e1 e2
deg (v3) = 4, since both e1 and e2 are incident on v3.
and the loop e3 is also incident on v3.
total degree of G = deg(v1) + deg(v2) + deg(v3) v3

=0+2+4
=6 e3
REMARK
The total degree of G, which is 6, equals twice the number of edges of G,
which is 3.

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)
The proof of the theorem is in the next page.

8
PROOF
Each edge “e” of G connects its end points vi and vj. This
edge, therefore contributes 1 to the degree of vi and 1 to the degree of vj.
If “e” is a loop, then it is counted twice in computing the degree of the
vertex on which it is incident.
Accordingly, each edge of G contributes 2 to the total degree of G.
Thus,
the total degree of G = 2. (the number of edges of G)

COROLLARY
The total degree of G is an even number.
NOTE:
Here you should remember the definition of even numbers “ Even
numbers are those numbers which are divisible by 2” Obviously the total
number of degree of a graph is an even number, because it has factor 2.

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

9
SOLUTION
(i) total degree of graph = 1 + 2 + 3 + 3
= 9 an odd integer
Since, the total degree of a graph is always even, hence no such graph is
possible.

(ii) Two graphs with four vertices of degrees 1, 2, 3 & 4 are

a
1. 2.
a b
b

c
d
c
d

The vertices a, b, c, d have degrees 1,2,3, and 4 respectively.

(iii) Suppose there were 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.

10
 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
Since, the total degree of graph = 2.(number of edges of graph)
 16 = 2.(number of edges of graph)
16
 Number of edges of graph = =8
2

EXERCISE

In a group of 15 people, is it possible for each person to have exactly 3

friends? Explain.
SOLUTION
Suppose that in a group of 15 people, each person had
exactly 3 friends. Then we could draw a graph representing each person by
a vertex and connecting two vertices by an edge if the corresponding people
were friends.
But such a graph would have 15 vertices each of degree 3, for a total degree
of 45 (not even) which is not possible.
Hence, in a group of 15 people it is not possible for each to have exactly
three friends.

11
 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.
The following are complete graphs K1, K2,K3, K4 and K5.

v1
v1 v2

K1 K2
v1

v2 v3
K3

v1 v4 v2

v1 v5

v2 v3 v3 v4
K4 K5
12
 EXERCISE

For the complete graph Kn, find

(i) the degree of each vertex
(ii) the total degrees
(iii) the number of edges
SOLUTION
(i) Each vertex v is connected to the other (n-1) vertices in Kn;
hence deg (v) = n - 1 for every v in Kn.
(ii) Each of the n vertices in Kn has degree n - 1; hence, the total degree in
Kn = (n - 1) + (n - 1) + … + (n - 1) n times
= n (n - 1)

(iii) Each pair of vertices in Kn determines an edge, and there are C(n, 2)
ways of selecting two vertices out of n vertices. Hence,
Number of edges in Kn = C(n, 2)

n(n − 1)
=
2
Alternatively,
The total degrees in graph Kn = 2 (number of edges in Kn)
 n(n-1) = 2(number of edges in Kn)
 Number of edges in Kn

n(n − 1)
=
2
13
 REGULAR GRAPH

A graph G is regular 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
REMARK The complete graph Kn is (n-1) regular.
Every complete graph is a regular graph.
EXERCISE
Draw two 3-regular graphs with six vertices.
SOLUTION
Note that there are so many graphs which can be made
three regular and we are drawing two of them.
a c b
a c

b f
f d
e d 14
e
 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.
The following are bipartite graphs

A B
v1 v2 v3
A v1 v4

v2 v5

v3 v6

B v4 v5

In it, you can partition the set of vertices in two subsets.

DETERMINING BIPARTITE GRAPHS

The following labeling procedure determines whether a graph is bipartite or

not.
1. Label any vertex a
2. Label all vertices adjacent to a with the label b.
3. Label all vertices that are adjacent to a vertex just labeled b
with label a.
4. Repeat steps 2 and 3 until all vertices got a distinct label (a bipartite
graph) or there is a conflict i.e. a vertex is labeled with a and b (not a
bipartite graph). 15
 EXERCISE

Find which of the following graphs are bipartite. Redraw the bipartite graph
so that its bipartite nature is evident.

SOLUTION
(i)
a

b b

a a,b (conflict)

The graph is not bipartite.

16
(ii) b a

a b

By labeling procedure, each vertex gets a distinct label. Hence the graph is
bipartite. To redraw the graph we mark labels a’s as a1, a2 and b’s as b1, b2,
b3 a1
b3

b1
a2 b2
Redrawing graph with bipartite nature evident.

b1
a1

b2

a2
b3

17
 COMPLETE BIPARTITE GRAPH

A complete bipartite graph on (m,n) vertices denoted Km,n is a simple graph

whose vertex set can be partitioned into two mutually disjoint non empty
subsets A and B containing m and n vertices respectively, such that each
vertex in set A is connected (adjacent) to every vertex in set B, but the
vertices within a set are not connected.

K2,3 K3,3

18