MA1002 – Computational Mathematics
Module – 5: Graphs- II
MA1002 – COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Module 5
Graphs II: Complement of a graph, Isomorphism of graphs, Walk, Trail,
Path, Cycle and circuit, Euler and Hamiltonian paths, Euler and
Hamiltonian graphs, Planar graphs, Graph colouring, Chromatic number.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Complement of a Graph
The complement 𝐺 ′ of a graph 𝐺(𝑉, 𝐸) is defined as a simple graph with the same
vertex set 𝑉, and two vertices 𝑢 and 𝑣 are adjacent only if they were not adjacent
in 𝐺; If they were adjacent then make them non-adjacent by deleting the edge.
Graph 𝐺 Graph 𝐺 ′
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Note: Isomorphism of Graphs
1. If the graph 𝐺 is a complete graph, Two graphs 𝐺1 𝑉1 , 𝐸1 and 𝐺2 𝑉2 , 𝐸2
then its complement graph is a null are said to be isomorphic, if there
graph. exist a mapping 𝑓: 𝑉1 → 𝑉2 such that
2. If 𝐺 is a 𝑛, 𝑚 simple graph, then (i) 𝑓 is a bijection (i.e. one – one and
the complement graph 𝐺 ′ has onto mapping)
𝑛(𝑛−1) (ii) If two vertices 𝑣𝑖 , 𝑣𝑗 𝜖𝑉1 are
− 𝑚 number of edges.
2
connected (adjacent) in 𝐺1 by an
3. If 𝐺 is a 𝑛, 𝑚 simple graph, and edge 𝑒1 𝜖𝐸1 then their images
degree of a vertex 𝑣 in 𝐺 is 𝑟, then
the degree of vertex 𝑣 in the 𝑓 𝑣𝑖 , 𝑓 𝑣𝑗 𝜖𝑉2 should be
complement graph 𝐺 ′ will be connected by an edge 𝑒2 𝜖𝐸2 in
𝑛−1−𝑟 . 𝐺2 .
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Determining when Graphs are not
This mapping 𝑓 is ,called isomorphism
Isomorphic
from the graph 𝐺1 to 𝐺2 .
(a) Find some property that two
We call that the graphs 𝐺1 and 𝐺2 are
isomorphic graph must have but the
isomorphic and denoted as 𝐺1 ≅ 𝐺2 .
two graph (under consideration) do
Important Note
not have. Like they have different
From the definition of isomorphism, we
number of vertices, edges, degree,
can conclude that if two graphs are
degree sequence etc.
isomorphic, then they have equal
(b) Sometimes two graphs have same
number of vertices & edges and equal
number of vertices and edges, but
number of vertices with given degree.
they are not isomorphic.
This is a necessary condition for
isomorphism.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
For this, attempt to classify the vertices in classes according to some property
preserved by isomorphism.
For example, we classify in to a single class, the vertices of degree 2 in each
graph and check these classes from a graph in their own right.
Ex. Consider the following graphs
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
The graph F and H have same number Let us consider a mapping
of vertices and edges, every vertex is of 𝑓: 𝑉(𝐹) → 𝑉(𝐺) such that,
degree 3, but the graph H has a 3-cycle 𝑓 1 = 1, 𝑓 2 = 5, 𝑓 3 = 3,
and the graph F does not have a 3- 𝑓 4 = 4, 𝑓 5 = 2, 𝑓 6 = 6
cycle.
So, F and H are not isomorphic.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
All the conditions of isomorphism
are satisfied, so F and G are
isomorphic graphs.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Ex. Check whether the following graphs are isomorphic or not?
Sol. Here 𝑉 𝐺1 = 1,2,3,4,5,6 and 𝑉 𝐺1 = 6
𝑉 𝐺2 = 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 and 𝑉 𝐺2 = 6
𝐸 𝐺1 = 1,2 , 1,3 , 1,4 , 2,3 , 2,5 , 3,6 , 4,5 , 4,6 , 5,6
𝐸 𝐺2
= 𝑣1 , 𝑣4 , 𝑣1 , 𝑣5 , 𝑣1 , 𝑣6 , 𝑣2 , 𝑣4 , 𝑣2 , 𝑣5 , 𝑣2 , 𝑣6 , 𝑣3 , 𝑣4 , 𝑣3 , 𝑣5 , 𝑣3 , 𝑣6
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Let us define a mapping 𝑓: 𝑉 𝐺1 → 𝑉 𝐺2 such that
𝑓 1 = 𝑣1 , 𝑓 2 = 𝑣2 , 𝑓 3 = 𝑣3 , 𝑓 4 = 𝑣4 , 𝑓 5 = 𝑣5 , 𝑓 6 = 𝑣6
This mapping is clearly a bijection.
Here 1,2 𝜖𝐸 𝐺1 but 𝑓 1 , 𝑓 2 = 𝑣1 , 𝑣2 ∉ 𝐸 𝐺2 .
So, the graphs 𝐺1 and 𝐺2 are not isomorphic.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Ex. Check that the following two graphs are isomorphic or not.
Sol. Here 𝑉 𝐺1 = 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 and 𝑉 𝐺1 = 5
𝑉 𝐺2 = 𝑢1 , 𝑢2 , 𝑢3 , 𝑢4 , 𝑢5 and 𝑉 𝐺2 = 5
𝐸 𝐺1 = 𝑣1 , 𝑣3 , 𝑣1 , 𝑣4 , 𝑣1 , 𝑣5 , 𝑣2 , 𝑣3 , 𝑣2 , 𝑣4 , 𝑣2 , 𝑣5
𝐸 𝐺2 = 𝑢1 , 𝑢2 , 𝑢1 , 𝑢4 , 𝑢1 , 𝑢5 , 𝑢2 , 𝑢3 , 𝑢3 , 44 , 𝑢3 , 𝑣5
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Vertex Degree Let us define a function𝑓: 𝑉 𝐺1 → 𝑉 𝐺2
𝑣1 , 𝑣2 3 Such that
𝑓 𝑣1 = 𝑢1 , 𝑓 𝑣2 = 𝑢3 , 𝑓 𝑣3 = 𝑢2 , 𝑓 𝑣4
𝑢1 , 𝑢3 3
= 𝑢4 , 𝑓 𝑣5 = 𝑢5
𝑣3 , 𝑣4 , 𝑣5 2 Which is clearly a bijection. Also,
𝑢 2 , 𝑢4 , 𝑢5 2
𝑣1 , 𝑣3 𝜖𝐸 𝐺1 and 𝑓 𝑣1 ,𝑓 𝑣3 = 𝑢1 , 𝑢2 𝜖𝐸 𝐺2 ∴ 𝐺1 ≅ 𝐺2
𝑣1 , 𝑣4 𝜖𝐸 𝐺1 and 𝑓 𝑣1 ,𝑓 𝑣4 = 𝑢1 , 𝑢4 𝜖𝐸 𝐺2
𝑣1 , 𝑣5 𝜖𝐸 𝐺1 and 𝑓 𝑣1 ,𝑓 𝑣5 = 𝑢1 , 𝑢5 𝜖𝐸 𝐺2
𝑣2 , 𝑣3 𝜖𝐸 𝐺1 and 𝑓 𝑣2 ,𝑓 𝑣3 = 𝑢3 , 𝑢2 𝜖𝐸 𝐺2
𝑣2 , 𝑣4 𝜖𝐸 𝐺1 and 𝑓 𝑣2 ,𝑓 𝑣4 = 𝑢3 , 𝑢4 𝜖𝐸 𝐺2
𝑣2 , 𝑣5 𝜖𝐸 𝐺1 and 𝑓 𝑣2 ,𝑓 𝑣5 = 𝑢3 , 𝑢5 𝜖𝐸 𝐺2
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Walk
A walk is defined as an alternate finite
sequence of vertices and edges,
starting and ending with vertices such
that each edge is incident with the
vertices which preceding and
succeeding it.
A vertex and an edge may appear
more than once in walk.
A walk is also referred to as an edge In the above graph,
train or a chain. 𝑣1 , 𝑎, 𝑣2 , 𝑏, 𝑣3 , 𝑐, 𝑣3 , 𝑑, 𝑣4 , 𝑒, 𝑣2 , 𝑓, 𝑣5 is
Vertices with which walk begins and a (𝑣1 − 𝑣5 ) walk.
ends are called terminal vertices. 𝑣1 , 𝑔, 𝑣3 , 𝑐, 𝑣3 , 𝑑, 𝑣4 is a (𝑣1 − 𝑣4 ) walk.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
A walk is said to traverse through Trail
vertices in sequence originating from In a walk, if the edges are distinct, then,
the initial vertex of the first edge and the walk is called as a trail.
ending at the terminal vertex of the last In other words, a trail is a walk without
edge in the sequence. repeating edges.
Open and Closed Walk Length of a Walk
In a walk, if terminal vertices are The number of edges involved in the
distinct, then, it is called an open walk. path is the length of the walk.
if terminal vertices are same, then, the Or it can be calculated as,
walk is called a closed walk. Length of walk = The number of
vertices in walk - 1
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Ex. For the following graph, find the
Sol. Length of the walk
length of the walk
= number of edges in the walk
𝑣0 , 𝑒1 , 𝑣1 , 𝑒2 , 𝑣2 , 𝑒3 , 𝑣4 , 𝑒6 , 𝑣0 , 𝑒5 , 𝑣5 .
=5
= number of vertices in the walk - 1
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Path
An open walk in which none of the
vertex is repeated is called a path.
For the adjacent graph,
𝑣1 , 𝑎, 𝑣2 , 𝑏, 𝑣3 , 𝑑, 𝑣4 , ℎ, 𝑣5 is an open
walk and so, it is a path from 𝑣1 to 𝑣5 .
Whereas
𝑣1 , 𝑎, 𝑣2 , 𝑏, 𝑣3 , 𝑐, 𝑣3 , 𝑑, 𝑣4 , 𝑒, 𝑣2 , 𝑓, 𝑣5 is
not a path as the vertex 𝑣3 is repeated.
The number of edges in a path is called
as the length of the path.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Important Notes Cycle and Circuit
1. A self-loop may be included in a A closed walk in which no vertex
walk but not in a path. (except terminal vertices) appears
2. The terminal vertices of a path are more than once, is called a circuit or a
of degree one and rest of the cycle.
vertices are of degree two. This i.e. A circuit is a non-intersecting walk.
degree is counted with respect to
the edges counted in the path not
in that graph, in which the path is
contained.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
In the adjacent graph, following are the
examples of circuits:
𝑣2 , 𝑏, 𝑣3 , 𝑑, 𝑣4 , 𝑒, 𝑣2 ;
𝑣3 , 𝑐, 𝑣3 ;
𝑣2 , 𝑒, 𝑣4 , ℎ, 𝑣5 , 𝑓, 𝑣2
Note:
1. Sometimes a circuit is referred to a
loop.
2. A self loop is always a circuit, but
the converse is not true.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Connected and Disconnected Graph
A graph G is said to be connected if
there exist atleast one path between
every pair of vertices in G. Otherwise
the graph G is disconnected.
The following graph is a connected
graph.
The above graph is a disconnected
graph.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Eulerian Graph
The graph G is said to have an Eulerian
tour if there is a closed walk such that
each edge of the graph appears exactly
once in the walk.
The graph G is said to be Eulerian if it
contains an Eulerian tour.
For a Eulerian graph, it is mandatory
that the closed walk must contain all
the edges of the graph exactly once but
not necessary that it will contain all the
vertices. (No boundation on vertices is Eulerian Graph
there)
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Non-Eulerian Graph Non-Eulerian Graph
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Th. A nonempty connected graph G is Hamiltonian Graph
Eulerian if and only if its all of vertices The connected graph G is said to be
are of even degree. Hamiltonian if there is a closed walk
OR such that it traverse through each
The necessary and sufficient condition vertex of the graph exactly once, except
for a nonempty connected graph to be the starting vertex, where the walk
Eulerian is that all the vertices of the terminates.
graph are of even degree. In considering the existence of
Hamiltonian graph, we need only
simple graph, as in Hamiltonian graph,
the walk traverses through every vertex
exactly once, so no chance of self-loop
and multiple edges.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Non-Hamiltonian Graph Non-Hamiltonian Graph
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Ex. Draw the graph which is
(i) Neither Eulerian nor Hamiltonian
(ii) Hamiltonian but not Eulerian
(iii) Eulerian but not Hamiltonian
(iv) Eulerian and Hamiltonian both.
Neither Eulerian nor Hamiltonian Hamiltonian but not Eulerian
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Eulerian but not Hamiltonian Eulerian and Hamiltonian both
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Planar Graph Ex. Find whether the following graph is
A graph G is said to be planar if there a planar graph or not.
exist a geometrical representation of G,
which can be drawn on plane such that
no two of its edges intersect.
[Meeting of edges at a vertex is not
considered as an intersection]
A graph that cannot be drawn on a
plane without crossover between its
edges is called a non-planar graph.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Sol. The given graph can be redrawn as Kuratowski’s Two Graphs
Th.1 The complete graph 𝐾5 on five
vertices is nonplanar.
Proof: Let 𝐺(𝑉, 𝐸) is a complete graph
with 5 vertices 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 and 𝑣5 .
We know that a complete graph is a
simple graph in which every vertex is
connected to the remaining each vertex
of the graph by means of an edge.
Therefore, we must have a circuit
𝑣1 to 𝑣2 to 𝑣3 to 𝑣4 to 𝑣5 to 𝑣1 . i.e. a
In this, none of the edge intersecting Pentagon.
other edge, so, the graph is planar.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
When we redraw the adjacent graph in
a plane with the efforts that none of
the edge intersects, it can be observed
that it is an impossible task.
Therefore, the complete graph on 5
vertices is a nonplanar graph.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Th. 2 The graph 𝐾3,3 (regular/complete When we redraw the adjacent graph in
bipartite) is nonplanar. a plane with the efforts that none of
Proof: The graph 𝐾3,3 can be drawn as the edge intersects, it can be observed
that it is an impossible task.
Therefore, the graph 𝐾3,3 is a
nonplanar graph.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Both the graphs 𝐾5 and 𝐾3,3 are called
Kuratowski’s graphs and it can be
noticed that
1. Both are regular graphs.
2. Both are nonplanar graphs.
3. Removal of one edge or vertex
makes them a planar graph.
4. First graph is a nonplanar graph
with the least number of vertices
and second graph is a nonplanar
graph with least number of edges.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Graph Coloring
A graph coloring is an assignment of
labels, called colors, to the vertices of a
graph such that no two adjacent
vertices of the graph share the same
colour.
Chromatic Number
The least number of colours required
for coloring of a graph G is called
chromatic number of the graph. It is
denoted by 𝜒(𝐺).
A graph is said to be k-chromatic if its
chromatic number is k.
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Ex. Find the chromatic number for the
following graph.
𝜒 𝐺 =3
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Ex. Find the chromatic number of the
Peterson graph (mentioned as following).
𝜒 𝐺 =3
MA1002 - COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Notes
1. Chromatic number of a null graph is 1.
2. Chromatic number of a complete graph 𝐾𝑛 is 𝑛.
3. If a graph is a circuit with 𝑛 vertices, then
(a) It is a 2-chromatic if 𝑛 is even
(b) It is a 3-chromatic if 𝑛 is odd
MA1002 – COMPUTATIONAL MATHEMATICS
Module 5: Graphs - II
Summary
In this topic, you learnt:
Concept of Graphs and basic terminology related to a
graph.
Concept of degree sequence, graphic, Havel-Hakimi
algorithm, Matrix representation of Undirected and
simple graphs.
Different types of graphs.
Concept of Graph coloring and Chromatic number.
THANK YOU