RV Institute of Technology & Management ®

MODULE-V

Graph Theory
Topic Learning Objectives:

Upon Completion of this unit, students will be able to:

1. Solve the various types of relations, functions and algebraic structures

2. Identify and justify the graph theory techniques to solve real world problems

Introduction to Graph Theory

Introduction to Graph Theory: Definitions and Examples, Sub graphs, Complements, and Graph
Isomorphism,

Directed Graphs

Look at the diagram shown below. This diagram consists of four vertices A, B, C, D and three
edges AB, CD, CA with directions attached to them, the directions being indicated by arrows.
Because of attaching directions to the edges, the edge AB has to be interpreted as an edge from
the vertex A to the vertex B and it cannot be written as BA. Similarly, the edge CD is from C to D
and cannot be written as DC, and the edge CA is from C to A and cannot be written as AC. Thus,
here, the edges AB, CD, CA are directed edges**.

Fig. directed graph

The directed edge AB is determined by the vertices A and B in that order and may therefore be
represented by the ordered pair (A, B). Similarly, the directed edges CD and CA may be
represented by the ordered pairs (C, D) and (C, A) respectively. Thus, the diagram in Figure
2.14 consists of a nonempty set of vertices, namely {A, B,C, D), and a set of directed edges

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 1 | 26

 RV Institute of Technology & Management ®

represented by ordered pairs of vertices taken from this set, namely {(A, B), (C, D), (C, A)}.
Such a diagram is called a diagram of a directed graph (or a Diagraph for brevity).
The formal definition of a directed graph is given below.

Definition of a Directed graph

A directed graph (or a digraph) is a pair (V, E), where V is a nonempty set and E is a
set of ordered pairs of elements. Taken from the set V.
For a directed graph (V, E), the elements of V are called vertices (points or nodes) and
the elements of E are called directed edges. The set V is called the vertex set and the set E
is called the directed edge set.
Thus, Figure 2.14 is a diagram of the directed graph for which the vertex set is

V = {A, B, C, D} and the edge set is E = {AB, CD, CA} = {(A, B), (C, D), (C, A)}.

Figure 2 depicts the directed graph for which the vertex set is V = {A, B, C, D} and the
edge set is E = {AB, CD, AC} = {(A, B), (C, D), (A, C)}.

Fig. directed graph

As illustrated in Figure 2.14, every directed edge of a digraph (directed graph) is determined by
two vertices of the digraph - a vertex from which it begins and a vertex at which it ends. Thus, if
AB is a directed edge of a digraph D, then it is understood that this directed edge begins at the
vertex A of D and terminates at the vertex B of D. Here, we say that A is the initial vertex and B
is the terminal vertex of AB. Equivalently, we say that AB is incident out of A and incident into
B.
It should be mentioned that for a directed edge (in a digraph) the initial vertex and
the terminal vertex need not be different. A directed edge beginning and ending at the
same vertex A is denoted by AA or (A, A) and is called a directed loop. The directed
edge shown in Figure 3 is a directed loop which begins and ends at the vertex A.

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 2 | 26

 RV Institute of Technology & Management ®

Fig. (a) self-loop (b) parallel directed graph& multiple parallel edges

A digraph can have more than one directed edge having the same initial vertex and the
same terminal vertex. Two directed edges having the same initial vertex and the same
terminal vertex are called parallel directed edges. Two parallel directed edges are shown
in Figure 2.16. Two or more directed edges having the same initial vertex and the same
terminal vertex are called multiple directed edges*. Three multiple edges are shown in
Figure 2.17.
A vertex of a digraph which is neither an initial vertex nor a terminal vertex of any
directed edge is called an isolated vertex of the digraph. A non-isolated vertex happens
to be an initial vertex or a terminal vertex for a (some) directed edge. A non-isolated
vertex which is not a terminal vertex for any directed edge is called a source and a non-
isolated vertex which is not an initial vertex for any directed edge is called a sink.

Fig. directed graph with isolated vertex

In the digraph shown in Figure 2.18, the vertex v4 is an isolated vertex, the vertices v 1 and v3
are sources and the vertex v2 is a sink. The vertices V5 and V6 do not belong to any of these
categories.
In-degree and Out-degree
If v is a vertex of a digraph D, the number of edges for which v is the initial vertex is called
the out-going degree or the out-degree of v and the number of edges for which v is the

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 3 | 26

 RV Institute of Technology & Management ®

terminal vertex is called the incoming degree or the in-degree of v. The out-degree of v is
denoted by 𝑑 + (v) or od(v) and the in-degree of v is denoted by d− (v) or id(v).
If follows that (i) 𝑑+ (v) = 0 if v is a sink, (ii) 𝑑− (v) = 0 if v is a source, and (iii) 𝑑 + (v) =
𝑑 − (v) = 0 if v is an isolated vertex.

Fig. directed graph with degree

For the digraph shown in Figure 2.19, the out-degrees and the in-degrees of the vertices
are as
given below:
𝑑 + (𝑣1 ) = 2, 𝑑 − (𝑣1 ) = 1, 𝑑 + (𝑣4 ) = 0, 𝑑 − (𝑣4 ) = 0,
𝑑 + (𝑣2 ) = 1, 𝑑 − (𝑣2 ) = 3, 𝑑 + (𝑣5 ) = 2, 𝑑 − (𝑣5 ) = 1,
𝑑 + (𝑣3 ) = 1, 𝑑 − (𝑣3 ) = 2, 𝑑 + (𝑣6 ) = 2, 𝑑 − (𝑣6 ) = 1,
We note that, in the above digraph, there is a directed loop at the vertex v3 and this loop
contributes a count 1 to each of 𝑑 + (𝑣3 ) and 𝑑 − (𝑣3 ).
We further observe that the above digraph has 6 vertices and 8 edges and that the sums of
the out-degrees and in-degrees of its vertices are

This illustrates the following property common to all digraphs. This property is referred to
as the First Theorem of the Digraph Theory.

Since every edge terminates at some vertex and since there are m edges, we should have
𝑟1 +𝑟2 + … + 𝑟𝑛 = m.
Accordingly,
𝑑 + (𝑣1 )+ 𝑑 + (𝑣2 ) + . . . +𝑑 + (𝑣𝑛 ) = 𝑟1 +𝑟2 + . . . + 𝑟𝑛 = m.

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 4 | 26

 RV Institute of Technology & Management ®

Similarly, if 𝑠1 is the number of edges coming into 𝑣1 , 𝑠1 is the number of edges coming
into 𝑣2 , and so on, we get
𝑑 − (𝑣1 )+ 𝑑 − (𝑣2 ) + . . . + 𝑑 − (𝑣𝑛 ) = 𝑠1 +𝑠2 + . . . + 𝑠𝑛 = m.

Thus,
Thus completes the proof.
Example 1: Find the in-degrees and the out-degrees of the vertices of the digraph shown in
Figure 2.18.

Fig. directed graph with degree

The given digraph has 7 vertices and 12 directed edges. The out-degree of a vertex is got
by counting the number of edges that go out of the vertex and the in-degree of a vertex is
got by counting the number of edges that end at the vertex. Thus, we obtain the following
data:

Vertex: 𝑣1 𝑣2 𝑣3 𝑣4 𝑣4 𝑣5 𝑣6

Out-degree: 4 2 2 1 3 0 0

In-degree: 0 1 2 2 1 2 4

This table gives the out-degrees and in-degrees of all vertices. We note that v1 is a source
and 𝑣6 and 𝑣7 are sinks.
We also check that,
sum of out-degrees = sum of in-degrees = 12 = No. of edges.
Definition of a Graph
A graph is a pair (V, E), where V is a nonempty set and E is a set of unordered pairs of
elements taken from the set V.
For a graph (V, E), the elements of V are called vertices (or points or nodes) and the
elements of E are called undirected edges or just edges. The set V is called the vertex set and
the set E is called the edge set.

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 5 | 26

 RV Institute of Technology & Management ®

A graph/digraph containing no edges is called a null graph. A null graph with only one
vertex is called a trivial graph. Figure 8 depicts a null graph with three vertices
A
•

B• •c

Fig. null graph

Order and Size

The number of vertices m a (finite) graph is called the order of the graph and the
number of edges in it is called its size. In other words, for a graph G = (V, E), the
cardinality of the set V, namely |V|, is called the order of G and the cardinality of the set E,
namely |E|, is called the size of G. A graph of order n and size m is called a (n, m) graph.
Thus, the graph depicted in Figure 2.18 is a (4.5) graph. A null graph with n vertices is a
(n, 0) graph.
End vertices, loop, multiple edges
Generally, the vertices of a graph are denoted by A, B, C, etc., or v1 , v2 , v3 , etc. When it is
convenient, we denote the edges of a graph by e1 , e2 , e3 , and so on. If vi and vj denote two
vertices of a graph and if ek denotes an edge joining vi and vj . then vi and vj are called the
end vertices (or end points) of ek . This is symbolically written as ek = {vi , vj } = vi vj. For
example, in the graph shown in Figure 2.18, suppose we denote the edges AB, BC, AC,
AD and DC by e1 , e2 , e3 , e4 and e5 respectively. Then e1 joins A and B; that is, e1 = {A,
B} = AB so that A and B are the end vertices of e1 . Similarly, e2 joins B and C; that is, e2
= {B, C} = BC, so that B and C are the end vertices of e2 , and so on.
Now, consider the graph shown in Figure 2.20. We note that this graph consists of four
vertices v1 , v2 , v3 , v4 , and six edges e1 , e2 , e3 , e4 , e5 , e6 . Although the edges e2 and e3 seem
to intersect (cross over) in the figure,* their point of intersection (even when it exists) is
not a vertex of the graph. We observe that the edges e1 , e2 , e3 have distinct end vertices,
but the edge 𝑒4 has the same vertex 𝑒3 as both of its end vertices; that is, 𝑒4 = {v3 , v3 }. An
edge such as 𝑒4 is called a loop. We also observe that both of the edges 𝑒5 and 𝑒6 have
the same end vertices 𝑣1 , 𝑣4 ; that is, 𝑒5 = {v1 , v4 } and 𝑒6 = {v1 , v4 }. Edges such as these are
called parallel edges. If in a graph there are two or more edges with the same end vertices,
the edges are called multiple edges.
I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 6 | 26
 RV Institute of Technology & Management ®

Fig. General graph

Simple graph, Multigraph, General graph

A graph which does not contain loops and multiple edges is called a simple graph. A graph which
does not contain a loop is called a loop-free graph. A graph which contains multiple edges but no
loops is called 𝒂 𝒎𝒖𝒍𝒕𝒊𝒈𝒓𝒂𝒑𝒉† . A graph which contains multiple edges or loops (or both) is called a
general graph.

Figure 2.21 represents a simple graph and Figure 9 represents a general graph. Figure 9
represents a multigraph.

Fig. Multigraph
Incidence
When a vertex v of a graph G is an end vertex of an edge e of the graph G, we say that the
edge e is incident on (or to) the vertex v. Since every edge has two end vertices, every
edge is incident on two vertices, one at each end. The two end vertices are coincident if
the edge is a loop.
When an edge e is incident on a vertex v, we also say that v is incident with e. Note that
whereas an edge is incident only on two vertices (namely its end vertices), a vertex may
be incident with any number of edges.
Two non-parallel edges are said to be adjacent edges if they are incident on a common
vertex (that is, if they have a vertex in common). Two vertices are said to be adjacent
vertices (or neighbors) if there is an edge joining them.
In the graph shown in Figure 2.22., A and B are adjacent vertices and 𝑒1 and 𝑒2 are adjacent
edges. But, A and C are not adjacent vertices, and 𝑒1 and 𝑒3 are not adjacent edges.
I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 7 | 26
 RV Institute of Technology & Management ®

Fig. Multigraph

Complete Graph
A simple graph of order ≥ 2 in which there is an edge between every pair of vertices is
called a complete graph (or a full graph).
In other words, a complete graph is a simple graph of order 2 in which every pair of
distinct vertices are adjacent.
A complete graph with n (≥ 2) vertices is denoted by 𝐾𝑛 .
Complete graphs with two, three, four and five vertices are shown in Figures 2.23(a) to
2.23(d) respectively. Of these complete graphs, the complete graph with five vertices,
namely 𝐾5 (shown in Figure 12(d)), is of great importance. This graph is called the
Kuratowski's first graph.

Fig. Complete graphs

Bipartite graph
Suppose a simple graph G is such that its vertex set V is the union of two of its mutually
disjoint nonempty subsets 𝑣1 and 𝑣2 which are such that each edge in G joins a vertex in 𝑣1 and a
vertex in 𝑣2 . Then G is called a bipartite graph. If E is the edge set of this graph, the graph is
denoted by G = (𝑣1 , 𝑣2 ; E), or G = G (𝑣1 , 𝑣2 ; E). The sets 𝑣1 and 𝑣2 are called bipartite (or
partitions) of the vertex set V.
For example, consider the graph G shown in Figure 13 for which the vertex set is V = {A,
B, C, P, Q, R, S} and the edge set is E = {AP, AQ, AR, BR, CQ, CS}. Note that the set V is
the union of two of its subsets 𝑣1 = {A, B, C} and 𝑣2 = {P, Q,R, S} which are such that (i) 𝑣1
and 𝑣2 are disjoint, (ii) every edge in G joins a vertex in 𝑣1 and a vertex in 𝑣2 , (iii) G
contains no edge that joins two vertices both of which are in 𝑣1 or 𝑣2 . This graph is a

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 8 | 26

 RV Institute of Technology & Management ®

bipartic graph with 𝑣1 = {A, B, C} and 𝑣2 = {P, Q, R, S} as bipartite.

Fig. Bipartite graph

Complete bipartite graph

A bipartite graph G = (𝑣1 , 𝑣2 ; E) is called a complete bipartite graph if there is an edge

between every vertex in 𝑣1 and every vertex in 𝑣2 .
The bipartite graph shown in Figure 12 is not a complete bipartite graph. Observe, for
example, that the graph does not contain an edge joining A and S.
*Named after the Polish mathematician Kasimir Kuratowski.
A complete bipartite graph G = (𝑣1 , 𝑣2 ; E) in which the bipartites 𝑣1 and 𝑣2 contain r and s
vertices respectively, with r ≤ s, is denoted by 𝑘𝑟,𝑠 . In this graph, each of r vertices in 𝑣1 is
joined to each of s vertices in 𝑣2 . Thus, 𝑘𝑟,𝑠 has r + s vertices and rs edges; that is 𝑘𝑟,𝑠 is
of order r + s and of size rs; it is therefore a (r + s, rs) graph.
Figures 2.25 (a) to 2.25 (d) depict some complete bipartite graphs. Observe that in Figure
9.2l(a), the bipartites are 𝑣1 = {A} and 𝑣2 = {P, Q, R}; the vertex A is joined to each
of the vertices P, Q, R by an edge. In Figure 13(b), the bipartite are 𝑣1 = {A} and 𝑣2
{M, N, P, Q, R}; the vertex A is joined to each of the vertices M, N, P, Q, R by an edge.

Fig. Complete Bipartite graph

In Figure 2.25(c), the bipartite are 𝑣1 = {A, B} and 𝑣2 = {P, Q, R}; each of the vertices A
and B is joined to each of the vertices P, Q, R by an edge". In Figure 2.25(d), the bipartite
are 𝑣1 = {A, B, C} and 𝑣2 = {P, Q, R}; each of the vertices A, B, C is joined to each of the
I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 9 | 26
 RV Institute of Technology & Management ®

vertices P, Q, R.
Of these complete bipartite graphs, the graph 𝑘3,3 shown in Figure 13(d) is of great
importance. This is known as the Kuratowski's second graph.
It is to be noted that a bipartite graph G is not a complete graph even if G is a complete
bipartite graph. Because, in such a graph, there exists no edge between two vertices if they
belong to the same bipartite.
Example 1. Let P, Q, R, S, T represent five cricket teams. Suppose that the teams P, Q,
R have played one game with each other, and the teams P, S, T have played one game with
each other. Represent this situation in a graph.
Hence determine (i) the teams that have not played with each other, and (ii) the number
of games played by each team.
Let the teams be represented by vertices and an edge represent the playing. Then the
graph representing the given situation is as shown in Figure 2.26:
We observe that there is no edge between Q and S , between Q and T , between R and S ,
and between R and T . Therefore, the teams Q and S , Q and T, R and S , and R and T have
not played with each other.
From the graph, we note that two edges are incident on each of the vertices Q, R, S , T and
four edges are incident on P. Thus, the teams Q, R, S, T have played two games each and the
team P has played four games.

Fig. Graph of cricket team

Example 2. Which of the following is a complete graph?

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 10 | 26

 RV Institute of Technology & Management ®

Fig. Graphs
The first of the graphs is not complete. It is not simple on the one hand and there is no
edge between A and C on the other hand. The second of the graphs is complete. It is a
simple graph and there is an edge between every pair of vertices.
1
Example 3. Show that a complete g raph with n vertices, namely 𝐾𝑛 , has 2n (n - 1) edges.

In a complete graph, there exists exactly one edge between every pair of vertices. As
such, the number of edges in a complete graph is equal to the number of pairs of
vertices. If the number of vertices is n, then the number of pairs of vertices is
n 𝑛! 1
C2 = (𝑛−2)!2! = 2n (n - 1)
1
Thus, the number of edges in a complete graph with n vertices is 2n (n - 1).

Example 4. Show that a simple graph of order n = 4 and size m = 7 and a complete graph of
order n = 4 and size m = 5 do not exist.
For n = 4, we have
1 1
n (n - 1) =2×4×3 = 6.
2

Since m = 7 exceeds this number, a simple graph of order n = 4 and size m = 7 does not
exist.
1
Similarly, since m = 5 is not equal to n(n - 1) = 6, a complete graph of order 4 and size
2

m = 5 does not exist.

Example 5. Which of the following is a bipartite graph?

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 11 | 26

 RV Institute of Technology & Management ®

Fig. Graphs
The first of the graphs is a bipartite graph, with V1 = {P, S} and V2 = {Q, R} as the bipartite.
The second graph is not a bipartite graph.
Example 6.
(a) How many vertices and how many edges are there in the complete bipartite graphs
K4,7 and K1,11?
(b) If the graph Kr,12 has 72 edges, what is r?
Sol: Recall that the complete bipartite graph Kr, s has r + s vertices and rs edges.
Accordingly:
(a) The graph K4,7 has 4 + 7 = 11 vertices and 4 x 7 = 28 edges, and the graph K 7,11 has
18 vertices and 77 edges
(b) If the graph Kr,12 has 72 edges, we have 12r = 72 so that r = 6

Vertex degree and Handshaking property

Let G = (V, E) be a graph and v be a vertex of G. Then, the number of edges of G that are
incident on v (that is, the number of edges that join v to other vertices of G) with the loops
counted twice is called the degree of the vertex v and is denoted by deg(v), or d(v).
The degrees of all vertices of a graph arranged in non-decreasing order is called the degree
sequence of the graph. Also, the minimum of the degrees of vertices of a graph is called the
degree of the graph.
For example, the degrees of vertices of the graph shown in Figure 2.29 are as given below.
d(v1) = 3, d(v2) = 4, d(v3) = 4, d(v4) = 3.
Therefore, the degree sequence of this graph is 3, 3, 4, 4, and the degree of the graph is 3.
Note that the loop at v3 is counted twice for determining the degree of v3.

Fig. Graph

Isolated Vertex, Pendant Vertex

A vertex in a graph which is not an end vertex of any edge of the graph is called an isolated
vertex. Obviously, a vertex is an isolated vertex if and only if its degree is zero.
I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 12 | 26
 RV Institute of Technology & Management ®

A vertex of degree 1 is called a pendant vertex. An edge incident on a pendant vertex is

called a pendant edge.
In the graph shown in Figure 18, the vertices v4 and V6 are isolated vertices, vs and v7 are
pendant vertices and the edges e4 and e5 are pendant edges.

Fig. Graph with Isolated Vertex, Pendant Vertex

As mentioned before, a null graph contains no edges. It therefore follows that in a null graph
every vertex is an isolated vertex.
Regular graph
A graph in which all the vertices are of the same degree k is called a regular graph of degree
k, or a k-regular graph.
In particular, a 3-regular graph is called a cubic graph.
The graphs shown in Figures 2.31 and 2.34 are 2-regular and 4-regular graphs respectively

Fig. 2-regular Graph Fig. 4-regular Graph

The graph shown in Figure 21 is a 3-regular graph (cubic graph). This particular cubic
graph, which contains 10 vertices and 15 edges, is called the Petersen graph.

Fig. 3-regular Graph

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 13 | 26

 RV Institute of Technology & Management ®

Handshaking Property

Let us refer back to the graph shown in Figure 2.29. As noted earlier, we have, in this
graph,

Also, the graph has 7 edges. We observe that

deg(v1) + deg(v2) + deg(v3) + deg(v4) = 14 = 2 x 7.
This observation illustrates the following important property common to all (finite) graphs.
Property: The sum of the degrees of all the vertices in a graph is an even number; and this
number is equal to twice the number of edges in the graph.
In an alternative form, this property reads as follows:
For a graph G = (V, E).

∑ deg(𝑣) = 2|𝐸|
𝑣∈𝑉

This property is obvious from the fact that while counting the degrees of vertices, each edge
is counted twice (once at each end).
The aforesaid property is popularly called the handshaking property.t Because, it essentially
states that if several people shake hands, then the total number of hands shaken must be
even, because just two hands are involved in each handshake.
The following theorem is a direct consequence of the handshaking property.
Theorem In every graph, the number of vertices of odd degrees is even.
Proof: Consider a graph with n vertices. Suppose k of these vertices are of odd degree so
that the remaining n - k vertices are of even degree. Denote the vertices with odd degree by
v1, v2 v3, . . . , Vk and the vertices with even degree by Vk+l • Vk+2• . . . , Vn. Then the sum of
the degrees of the vertices is
𝑛 𝑘

∑ deg(𝑣𝑖) = ∑ deg(𝑣𝑖)
𝑖=1 𝑖=1

In view of the hand shaking property, the sum on the left hand side of the above expression
is equal to twice the number of edges in the graph. As such, this sum is even. Further, the
second sum in the right hand side is the sum of the degrees of vertices with even degrees. As
such, this sum is also even. Therefore, the first sum in the right hand side must also be even,
that is,
deg(vi) + deg(v2) + ···+ deg(vk) = even
I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 14 | 26
 RV Institute of Technology & Management ®

But, each of deg(v1), deg(v2), . . . , deg(vk) is odd. Therefore, the number of terms in the left
hand side of (2) must be even, that is, k is even.
This completes the proof of the theorem. •
Note: According to the above theorem, in any graph, there is an even number of vertices of
odd degrees. But, it is not true in general that a graph must have an odd number of vertices
of even degrees. Observe that the graph shown in Figure 9.33 has an even number of
vertices of even degrees.
Example 1. For the graph shown in Figure 2.34, indicate the degree of each vertex an verify
the handshaking property:

Fig. Graph
By examining the graph, we find that the degrees of its vertices are as given below:
deg(a) = 3, deg(b) = 2, deg(c) = 4,
deg(d) = 2, deg(e) = 0, deg(f) = 2,
deg(g) = 2, deg(h) = 1.
We note that e is an isolated vertex and h is a pendant vertex.
Further, we observe that the sum of the degrees of vertices is equal to 16. Also, the
graph has 8 edges. Thus, the sum of the degrees of vertices is equal to twice the number of
edges.
The verifies the handshaking property for the given graph
Example 2. Can there be a graph consisting of the vertices A, B, c, D with deg(A) = 2,
deg(B) = 3, deg(C) = 2, deg(D) = 2?
Sol: In every graph, the sum of the degrees of the vertices has to be an even number. Here,
this sum is 9 which is not even. Therefore, there does not exist a graph of the given kind.
Example 3. Can there be a graph with 12 vertices such that two of the vertices have degree
3 each and the remaining 10 vertices have degree 4 each?
Sol: Here, the sum of the degrees of vertices is (3 x 2) + (4 x 10) = 46. Therefore, if m = 23,
we have 2m = 46 and the handshaking property holds. Hence there can be a graph of the
desired type (whose size is 23).
Example 4. Prove that the k-dimensional hypercube Qk has k2k-l edges.
I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 15 | 26
 RV Institute of Technology & Management ®

Determine the number of edges in Q 8 .

In the hypercube Qk. the number of vertices is 2k and each vertex is of degree k.
Therefore, the sum of degrees of vertices of Qk is k x 2k. By handshaking property, we
should have
1
k x 2k = 21|EI, where IEI is the size of Q k . Thus, IEI = 2(k x 2k ) = k x 2k-1 . This means that Qk

has k2k-1 edges.

It follows that the number of edges in Q8 is 8 x 27 = 1024.

Example 5. What is the dimension of the hypercube with 524288 edges?
How many vertices are there in a hypercube with 4980736 edges?
For the k-dimensional hypercube Qk. the number of vertices is 2k and the number of edges is
k2k-l.
If Qk has 524288 edges, we have k2k-l = 524288. We check that

524288 = 219 = 24 x 215 = 16 x 215.

Accordingly, k2k-l = 524288 holds if k = 16. Thus, the dimension of the hypercube with
524288 edges is k = 16.
We check that 4980736 = 19 x 218, which indicates that Qk has 4980736 edges when k = 19.
The number of vertices in this hypercube is 2k = 219 = 524288.

Example 6. Determine the order |V| of the graph G = (V, E) in the follow cause:
1. G is a cubic graph with 9 edges.
2. G is regular with 15 edges.
3. G has 10 edges with 2 vertices of degree 4 and all other vertices of degree 3.
(1) Suppose the order of G is n. Since G is a cubic graph, all vertices of G have degree
3, and therefore the sum of the degrees of vertices is 3n. Since G has 9 edges, we
should have 3n = 2 x 9 (by the handshaking property) so that n = 6. Thus, the order of
G is 6.
(2) Since G is regular, all vertices of G must be of the same degree, say k. If G is of
order n, then the sum of the degrees of vertices is kn. Since G has 15 edges, we
should have kn = 2 x 15 so that k = 30/ n. Since k has to be a positive integer, it
follows that n must be a divisor of 30. Thus, the possible orders of G are 1,2, 3, 5, 6,
10, 15 and 30.
(3) Suppose the order of G is n. Since two vertices of G are of degree 4 and all others are
I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 16 | 26
 RV Institute of Technology & Management ®

of degree 3, the sum of the degrees of vertices of G is 2 x 4 + (n - 2) x 3. Since G has

10 edges, we should have 2 x 4 + (n - 2) x 3 = 2 x 10. This gives n = 6. Thus, the
order of G is 6.
Example 7. let G be a graph of order 9 such that each vertex has degree 5 or 6. Prove that at
least 5 vertices have degree 6 or at least 6 vertices have degree 5.
Let p be the number of vertices of G which have degree 5. Then the number of vertices of G
which have degree 6 is 9– p= q(say). Evidently 0 ≤ p ≤ 9, 0 ≤ q ≤ 9.
We know that the sum of the degrees of vertices of G is
(5 x p) + (6 x q) = 5 p + 6(9 - p) = 54 – p
Since this sum has to be an even number, p cannot be odd. Thus, p = 0, 2, 4, 6, or 8.
Consequently, the following possible cases arise
p = 0, q = 9
p = 2, q = 7
p = 4, q = 5
p = 6, q = 3
p = 8, q = 1
We observe that in all the above possible cases either q ≥ 5 or p ≥ 6. This means that atleast
5 vertices have degree 6 or atleast 6 vertices have degree 5.

Example 8. Show that there is no graph with 28 edges and 12 vertices in the following cases.
(i) The degree of a vertex is either 3 or 4.
(ii) The degree of a vertex is either 3 or 6.
Suppose there is a graph with 28 edges and 12 vertices, of which k vertices are of degree 3
(each). Then:
(i) If all of the remaining (12 — k) vertices have degree 4, then we should have (by the
= 56, or k —8 which is not possible handshaking property) 3k + 4(12 — k) 2 x 28 (because
has to be nonnegative).
(ii) If all of the remaining (12—k) vertices have degree 6, then we should have 3k+6(12—k) =
56, or k = 16/3. This is not possible (because k has to be a nonnegative Integer).
Hence, in both of the two given cases, the graph of the desired type cannot exist.
Example 9. (a) Show that in a complete graph of n vertices (namely Kn) the degree of
1
every vertex is (n — 1) and that the total number of edges is 2 𝑛(n — l).

(a) If Kn has m edges, show that n(n + l) + m).

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 17 | 26
 RV Institute of Technology & Management ®

(a) Recall that a complete graph is a simple graph in which every vertex is joined with
every other vertex through exactly one edge. Therefore, if there are n vertices, each vertex is
joined to (n— I) vertices through exactly one edge. Thus, there occur n— I edges at every
vertex. This means that the degree of every vertex is n — 1.
Consequently, the sum of the degrees of vertices is n (n — 1). By handshaking property,
this sum must be equal to 2m, where m is the number of edges. Thus, n (n— l) = 2m, or
1 1
m = 2 𝑛 — l). Thus, Kn has 2 𝑛 (n- l) edges.
1
(b) If Kn has m edges, then we have, from what has been just proved, m = 2 𝑛 - 1). This
1
gives n + m = n+2n (n -1), or 2 (n+m) = 2n+n —n2 –n =n (n+ 1).

Remark: since the degree of every vertex in kn is a (n – 1) - regular graph.

Isomorphism

Consider two graphs G = (V, E) and G' = (V' , E' ). Suppose there exists a function f: V V'
such that (i) f is a one-to-one correspondence*, and (ii) for all vertices A, B of G, {A, B) is
an edge of G if and only if {f(A), f (B)} is an edge of G'. Then f is called an isomorphism
between G and G', and we say that G and G' are isomorphic graphs.
In other words, two graphs G and G' are said to be isomorphic (to each other) if there is a
one-to-one correspondence between their vertices and between their edges such that the
adjacency of vertices is preserved. Such graphs will have the same structure; they differ
only in the way their vertices and edges are labeled or only in the way they are represented
geometrically. For many. purposes, we regard them as essentially the same graphs.
When G and G' are isomorphic, we write G = G'.
When a vertex A of G corresponds to the vertex A' = f (A) of G' under a one-to-one
correspondence f: G →t G', we write A ↔ A'. Similarly, we write {A, B) ↔ {A', B') to mean
that the edge AB of G and the edge A' B' of G' correspond to each other, under f.
For example, look at the two graphs shown in Figure 2.34.

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 18 | 26

 RV Institute of Technology & Management ®

Fig. Graph
Consider the following one-to-one correspondence between the vertices of these two graphs:
A ↔ P, B ↔ Q, C ↔ R, D ↔ S.
Under this correspondence, the edges in the two graphs correspond with each other, as
indicated below:
{A, B) ↔ {P, Q}, {A, C} ↔ {P, R), {A, D) ↔ {P, S},
{B, C) ↔ {Q, R), { B, D) ↔ {Q,S}, {C, D} ↔ {R,S}.
We check that the above-indicated one-to-one correspondence between the vertices/edges of
the two graphs preserves the adjacency of the vertices. The existence of this correspondence
proves that the two graphs are isomorphic. (Note that both the graphs represent the complete
graph K4)
Next, consider the two graphs show in figure 2.35.

Fig. Graphs
We observe that both of these two graphs have the same number of vertices but different
number of edges. Therefore, although there can exist one-to-one correspondence between
the vertices, there cannot be a one-to-one correspondence between the edges. The two
graphs are therefore not isomorphic.
From the definition of isomorphism of graphs, it follows that if two graphs are isomorphic,
then they must have:
1. The same number of vertices
2. The same number of edges
3. An equal number of vertices with a given degree
These conditions are necessary but not sufficient. This means that two graphs for which

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 19 | 26

 RV Institute of Technology & Management ®

these conditions hold need not be isomorphic. (See Example 8 below)

In particular, two graphs of the same order and the same size need not be isomorphic. To see
this, consider the two graphs shown in Figure 2.36.

Fig. Graphs

We note that both of these graphs are of order 4 and size 3. But the two graphs are not
isomorphic. Observe that there are two pendant vertices in the first graph whereas there are
three pendant vertices in the second graph. As such, under any one-to-one correspondence
between the vertices and the edges of the two graphs, the adjacency of vertices is not
preserved. It is not hard to realize that every two complete graphs with the same number of
vertices, n, are isomorphic. For this reason, we speak of the complete graph of n vertices,
and all complete graphs with n vertices are denoted by Kn.
Similarly, any two complete bipartite graphs with bipartites containing r and s vertices are
isomorphic. For this reason, all complete bipartite graphs with bipartites containing r and
s vertices are denoted by Kr,s·
Given two graphs G and G', there is no set precedure for proving or disproving that they are
isomorphic. It is only by carefully examining the nature of vertices and edges of both G and
G' that one can find whether or not they are isomorphic. If G and G' are not isomorphic, it is
relatively easy to find it out. If G and G' are isomorphic, the work involved in proving it is
quite hard - it gets harder as the orders and sizes of G and G' get larger.
Isomorphism of digraphs.
The definition of isomorphism of graphs can be extended to digraphs in a natural way. Two
digraphs D1 and D2 are said to be isomorphic if there is a one-to-one correspondence
between their vertices and between their edges such that adjacency of vertices along with
directions is preserved.
Example 10. Prove that the two graphs shown below are isomorphic.

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 20 | 26

 RV Institute of Technology & Management ®

Fig. Graphs
We first observe that both graphs have four vertices and four edges. Consider the fo1lowing
one-to-one correspondence between the vertices of the graphs:
u1 ↔v1 , u2 ↔v4, u3 ↔ v3, u4 ↔v2
This correspondence gives the following correspondence between the edges:
{u1, u2} ↔ {v1, v4}, {u1, u3} ↔ {v1, v3},
{u2, u4} ↔{v 4, v2}, {u3, u4} ↔ { v3, v2}.

Example 11. Verify that the two graphs shown below are isomorphic.

Fig. Graphs
Let us consider the one-to-one correspondence between the vertices of the two graphs under
which the vertices A, B, C, D, P, Q, R, S of the first graph correspond to the vertices A’, B’,
C', D', P', Q', R', S' respectively of the second graph, and vice-versa. In this correspondence,
the edges determined by the corresponding vertices correspond so that the adjacency of
vertices is retained. As such, the two graphs are isomorphic.
We note that the first graph is the hypercube Q3; see Figure 2.38. The second graph is just
another drawing of Q3.
Example 12. Show that the following two graphs are isomorphic:

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 21 | 26

 RV Institute of Technology & Management ®

Fig. Graphs
We first note that both the graphs have six vertices each of degree three, and nine edges.
Bearing the edges in the two graphs in mind, consider the correspondence between the
edges as shown below.
{u1, u4} ↔ {v1, v2}, {u1, u5} ↔ {v1, v5}, {u1, u6} ↔ {v1, v6}
{u2, u5} ↔ {v4, v3}, {u2, u4} ↔ {v4, v2}, {u2, u6} ↔ {v4, v6}
{u3, u6} ↔ {v5, v6}, {u3, u4} ↔ {v5, v2}, {u3, u5} ↔ {v5, v3}
These yields the following correspondence between the vertices:
u1↔v1, u2↔v4, u3↔v5.
u4↔v2, u5↔v3, u6↔v6.
We observe that the above correspondences between the edges and the vertices are one-to-
one correspondences and that these preserve the adjacency of vertices. In view of the
existence of these correspondences, we infer that the two graphs are isomorphic.
We note that the first graph is the complete bipartite graph K3,3; see Figure 2.39. The second
graph is just another drawing of K3 ,3.
Example 13. Show that the following two graphs are isomorphic.

Fig. Graphs
We first note that each of the two graphs is 3-regular (cubic) and has 10 vertices. Consider
the one-to-one correspondence between the vertices as shown below:
vi ↔ ui , for i = 1, 2, 3, . . . , 10.
This correspondence has been arrived at after closely examining the structures of the two
graphs.
I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 22 | 26
 RV Institute of Technology & Management ®

We check that the above mentioned correspondence yields one-to-one correspondence

between the edges in the two graphs with the property that adjacent vertices in the first
graph correspond to the adjacent vertices in the second graph and vice-versa. The two
graphs are therefore isomorphic.
We note that the first graph is the Petersen graph, see Figure 2.40. The second graph is just
another drawing of the Petersen graph.

Example 14. Show that the following graphs are not isomorphic.

Fig. Graphs
We observe that the first graph has 4 vertices and 6 edges and the second graph has 4
vertices and 7 edges. As such, one-to-one correspondence between the edges is not possible.
Hence the two graphs are not isomorphic.

Example 15. Show that the following graphs are not isomorphic.

Fig. Graphs
We note that each of the two graphs has 6 vertices and 9 edges. But, the first graph has 2
vertices of degree 4 whereas the second graph has 3 vertices of degree 4. Therefore, there
can- not be any one-to-one correspondence between the vertices and between the edges of
the two graphs which preserves the adjacency of vertices. As such, the two graphs are not
isomorphic.
Example 16. Show that the following graphs are not isomorphic.

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 23 | 26

 RV Institute of Technology & Management ®

Fig. Graphs
We note that the first graph has a pair of vertices of degree 4 which are not adjacent whereas
the second graph has a pair of vertices of degree 4 which are adjacent. (The reader is
required to identify them!). Therefore the two graphs are not isomorphic.
Example 17. Show that two graphs need not be isomorphic even if they have the same number
of vertices, the same number of edges and equal number of vertices with the same degree.
Consider the two graphs shown in Figure 32:
We observe that both graphs have the same (6) number of vertices and the same (5) number
of edges. Further, in each of them there are 3 vertices of degree 1 (namely, v1, v5, v6 in
the first graph and A, P, R in the second graph), there are 2 vertices of degree 2 (namely,
vz, v 3 in the first graph and B, Q in the second graph), and there is 1 vertex of degree 3
(namely, v4 in the first graph and C in the second graph). Thus, the two graphs have equal
number of vertices with the same degree.

Fig. Graphs

But, the two graphs are not isomorphic. Because there are 2 pendant vertices adjacent to the
vertex v4 (which is of degree 3) in the first graph but there is only one pendant vertex
adjacent to the-vertex C (which is of degree 3) in the second graph. As such, the adjacency
of vertices cannot be preserved under a one-to-one correspondence between the vertices of
the graphs.

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 24 | 26

 RV Institute of Technology & Management ®

Example 18. Show that the following digraphs are isomorphic.

Fig. Graphs
Consider the following one-to-one correspondence between the vertices of the given di-
graphs:
A ↔ Q, B ↔ P, C ↔ S, D ↔R.

Under this correspondence, the directed edges of the two graphs correspond with each other
as shown below.
A, B) ↔ (Q, P), (B, C) ↔ (P, S), (C, D) ↔ (S, R), (D, A) ↔ (R, Q).
Evidently, under this correspondence, the adjacency of vertices including directions of the
edges is preserved.
Hence the given digraphs are isomorphic.
Example 19. Show that the following digraphs are not isomorphic.

Fig. Graphs
The two digraphs have the same number of vertices (5) and the same number of directed
edges (7). We observe that the vertex A of the first digraph has 1 as its out-degree and 2 as
its in-degree. There is no such vertex in the second digraph. Therefore, there cannot be any
one- to-one correspondence between the vertices of the two digraphs which preserves the
direction of edges. The two digraphs are therefore not isomorphic.

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 25 | 26

 RV Institute of Technology & Management ®

Video Links:

[Link]

[Link]

[Link]

[Link]

I-Semester: Mathematical Foundation for computer Applications (22MCA11) P a g e 26 | 26