Module 1 (10 hours):
Introduction to Graphs, Isomorphism, Directed graphs. Subgraphs: Spanning Subgraphs, Induced Subgraphs, vertex and edge deleted Subgraphs. Operations on graphs.

Module 2 (10 hours):
Walk, Trails and Paths, connected graphs, disconnected graphs, Bipartite graphs, Cycles, Eulerian graphs, Euler Theorem, Hamiltonian path, Hamiltonian graphs, Dirac’s Theorem, Ore’s Theorem, Trees, Spanning Trees.

Module 3 (10 hours):
Algorithms on graphs, shortest path Algorithms: Dijkstra’s Algorithm, Minimal Spanning Tree, Breadth First Search Algorithm, Depth First Search Algorithm.Matrix Representation of graphs, Incidence matrix, Adjacency Matrix, Laplacian Matrix, Eigenvalues of Adjacency and Laplacian Matrix.

Module 4 (10 hours):
Vertex and Edge connectivity, Whitney’s Inequality, Colouring of graph, Chromatic number, Chromatic polynomial, Edge contraction, Plane and Planar graphs, Embedding and Regions, Euler’s Formula, Kuratowski’s Theorem, Colouring planar graphs, The Four-Color Theorem, The Five-Colour Theorem.

The course treats graph-theoretical notions and problems, and the use of algorithms, both in the mathematical theory of graphs and its applications.

In the course, the basic theory of graphs of different kinds are developed in detail, especially trees and bipartite graphs.

Algorithms that totally or partly solve graph-theoretical problems are presented.

The theory of vertex, edge connectivity and the coloring problems are also introduced.

CO1: Students become familiar with the basic notions of graph theory.
CO2: They develop skills to apply the theorems and algorithms that are treated in the course for solving graph theoretical problems.
CO3: Students learn the connectivity and coloring problems, and their applications to various situations.
CO4:
CO5:

Adrian Bondy, U.S.R. Murty, Graph Theory, Springer London , Graduate Texts in Mathematics, 2008.

Douglas B. West, Introduction to Graph Theory, Prentice Hall India , 2nd Edition, 2002.

R. Diestel, Graph Theory, Springer , Graduate Texts in Mathematics, 1997.

Frank Harary, Graph Theory, CRC Press , 1st Edition, 1969.