Graph Theory


Dr. Bhairaba Kumar Majhi


Core Courses

Course Attendees

Still no participant

Course Reviews

Still no reviews

Course Name : Graph theory

Code(Credit) : CUTM-1531(3-1-0)

Course Objectives

  • To introduce the students to graphs, their properties and their applications as models of networks.

  • To represent almost any physical situation involving discrete objects and a relationship among them.

  • To introduce the students to generating functions and their applications.

Course Outcomes

COs Course outcomes Mapping Cos with POs (High-3, Medium-2, Low-1)
CO1 Know the basic definitions and concepts of graph theory and Write in a coherent and technically accurate manner.


PO1(3), PO2(2)
CO2 Learn about how to develop graph theoretical algorithm and Know about many different coloring problems for graphs.


PO2(2), PO9(2)

Course Syllabus


Introduction to Graphs and Definition of graphs;Basic terminologies and types of graphs;Degree of a vertex,Isolated and Pendent vertices;Sub graphs and graph Isomorphism.

Practice 1: Determine if two graphs are isomorphic and identify the isomorphism


Directed Graphs and Types of Digraphs;Out-degree, In-degree, Connectivity and Orientation;Digraphs and Binary relations , Directed paths and contentedness;Euler Digraphs, De-Brujin sequences;Tournaments.

Practice 2:  Ways to Represent Graphs using Python


Basic concepts of Planar Graphs; Kuratowski’s Two graphs ;Representation of Planar Graphs ; Detection of planarity ;Euler’s formula for planar graphs;

Practice 3: A look in to Planar Graphs and Euler's Relationship


Distance, cut-vertices, cut-edges, blocks;weighted graphs, connectivity;Dijkstra’s shortest path algorithm;Floyd-War shall Shortest path algorithm; 


Proper Coloring of graphs;Chromatic numbers of a graph;Chromatic polynomial;Chromatic Partitioning;Four Colour theorem.

Practice 4: Finding Chromatic number using python-networks.


Definition and properties of trees;Rooted and Binary trees; Counting trees, Spanning trees;

Practice 5: Applications of graphs with Euler and Hamiltonian path and circuits(Chinese postman Problem)


Minimum spanning trees;Fundamental Circuit;Cut set and Separability;

Practice 6: Application of Minimum spanning tree in  a Net work model

Text Book:

Deo, N., “Graph Theory with Applications to Engineering and Computer Science”, Prentice Hall India 2004

Chapters: 1(1.1,1.2,1.3,1.4,1.5) ,2 (2.1,2.2,2.4,2.4,2.6,2.9), 3(3.1,3.2,3.5,3.7,3.8,3.9,3.10), 4(4.1,4.4,4.5), 5(5.2,5.3,5.4,5.5), 7(7.1,7.2), 8(8.1,8.2,8.3,8.6),9(9.1,9.2,9.3,9.4,9.5)

Reference Books:

West, D. B., "Introduction to Graph Theory ", Prentice Hall India (2nd Edition 2009)

Aldous, J. M., Wilson, R. J. and Best S., “Graphs and Applications: An Introductory Approach”, Springer2003.

Deistel, R., “Graph Theory”, Springer (4th Edition) 2010.

Chartrand, G. and Zhang, P., "Introduction to Graph Theory", Tata McGraw Hill2007.

Bondy, J. A. and Murty, U. S. R., “Graph Theory”, Springer 2011

Session Plan

Session 1:

Introduction to Graphs and Definition of graphs.

Session 2:

Basic terminologies  of graph and types of graphs.


Session 3:

Session 4:

Sub graphs and graph Isomorphism

Session (5 & 6):

practice 1:

An Introduction to Graph Neural Networks: Models and Applications

Session 7:

Directed Graphs and Types of Digraphs

Session 8:

Session 10:

Directed paths and connectedness,

Session 11:

Euler Digraphs, De-Brujin sequences,

Session (12 & 13):

practice 2:

Ways to Represent GRAPHS using Python


Session 15:

Basic concepts of Planar Graphs,

Session 19:

Euler’s formula for planar graphs

Session (20 & 21):

practice 3:

A look in to Planar Graphs and Euler's Relationship

Session 22:

Distance, cut-vertices, cut-edges, blocks

Session 23:

weighted graphs, connectivity

Session (26 & 27):

practice 4:

Chromatic number using python-networkx|Graph Theory|Chromatic number of a graph

Session 28:

Session 29:

Chromatic numbers of a graph.

Session 30:

Session 31:

Session (33 & 34):

practice 5:

Applications of graphs with Euler and Hamiltonian path and circuits(Chinese postman Problem)


Session 35:

Definition and properties of trees

Session 37:

Counting trees, Spanning trees.

Session 39:

Session 41 &42:

practice 6:

Application of Minimum spanning tree in  a Net work model

Counting Spanning Trees using python-networkx| Graph Theory|Kirchoff's Matrix Tree Theorem

practice 7:

Binary Tree , basic introduction and Code implementation to create tree in Python

practice 8:

Binary Trees in Python: Level-order Traversal



Case Studies

Case Studies

Our Main Teachers

My Self Dr.Bhairaba Kumar Majhi,M,Sc,B.Ed,M.Tech(CSE),Ph.D(Mathematics ) ,Asst.Professor And HOD Department of Mathematics School Of Applied Sciences,Presently working at CUTM,Bolangir Campus.I have 16 Years of Experience in Teaching at Different Levels Of UG,PG & Engineering Mathematics.