Back


CS60047 Advanced Graph Theory

(Autumn Semester 2026)

Arobinda Gupta
Bivas Mitra

Teaching Assistants
Aman Antil aman200 [AT] kgpian.iitkgp.ac.in

Notices
21.07.2026 First class: July 23, 2026, Thursday. Time: 14.00, Venue: CS-107.
       Course outline
       General Information
       Lectures
       Evaluation

Course outline

 Graphs provide a powerful mathematical framework for modeling and solving problems involving interconnected entities, making them indispensable in computer science, artificial intelligence, communication networks, transportation systems, social networks, bioinformatics, and optimization. This course introduces the fundamental concepts of graph theory and gradually advances towards sophisticated graph algorithms, optimization techniques, and real-world applications. The course begins with the mathematical foundations of graphs, including graph representations, traversals, connectivity, trees, and graph properties. It then explores classical algorithmic problems such as shortest paths, minimum spanning trees, graph coloring, matchings, network flows, Eulerian and Hamiltonian graphs, planar graphs, and graph decompositions. The course further introduces advanced topics including graph embeddings, spectral graph theory, random graphs, graph mining, graph databases, and large-scale graph processing. Special emphasis will be placed on designing efficient graph algorithms, analyzing their computational complexity, and applying graph-theoretic techniques to solve practical problems arising in communication networks, social networks, recommendation systems, transportation, biological networks, and modern data analytics. Through theoretical foundations, algorithmic techniques, and case studies, students will gain a comprehensive understanding of graph-based problem solving and develop the skills required to model and analyze complex networked systems.

This course assumes familiarity with basic data structures, algorithms and discrete mathematics.

Syllabus

 Graph Fundamentals: Introduction to graph theory, graph terminology, graph representations, graph isomorphism, graph operations, directed and undirected graphs, weighted and unweighted graphs, bipartite graphs, complete graphs, graph complements, graph metrics, connected components, articulation points, bridges, graph decomposition.
Graph Connectivity and Traversability: Walk, Trail, Path, Cycle, Vertex and edge connectivity, cut vertices, edge cuts, biconnected and strongly connected components, Menger's theorem, Eulerian paths and circuits, Fleury's algorithm, Hamiltonian paths and cycles, Chinese Postman Problem, Traveling Salesman Problem, graph traversal optimization.
Trees: Properties and characterization of trees, rooted and ordered trees, spanning trees, tree centers and centroids, tree isomorphism, Prüfer sequences, fundamental tree properties and applications.
Bipartite Graphs: Properties and characterization of bipartite graphs, complete bipartite graphs, graph bipartiteness testing, Hall's Marriage Theorem, König's theorem, applications in scheduling, assignment, and network modeling.
Graph Coloring: Vertex coloring, edge coloring, chromatic number, chromatic polynomial, greedy coloring algorithms, Brooks' theorem, scheduling and register allocation, map coloring, applications in frequency assignment, timetabling, and resource allocation.
Graph Matchings: Matchings in graphs, maximum and perfect matchings, bipartite matchings, Hall's Marriage Theorem, König's theorem, Hungarian algorithm, stable matching, augmenting paths, applications in assignment problems, resource allocation, and network design.
Covering and Independent Sets: Vertex and edge covers, minimum vertex cover, minimum edge cover, independent sets, maximum independent sets, clique–independent set relationship, König's theorem, and applications.
Network Flow: Flow networks, maximum flow problem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, minimum cut theorem, circulation problems, multi-commodity flow, assignment problems, matching-flow relationships, applications in logistics, communication networks, and resource management.
Planar Graphs and Graph Embedding Planar graphs, Euler's formula, graph planarity testing, Kuratowski's theorem, graph embeddings, graph drawing techniques, dual graphs, map coloring theorem, applications in VLSI design and geographic information systems.

Text Books:
1. Introduction to Graph Theory, Douglas B. West, Prentice Hall.

2. Graph Theory, Reinhard Diestel, Springer. 

3. Graph Theory with Applications, J. A. Bondy and U. S. R. Murty, Elsevier/North-Holland. 

4. Algorithmic Graph Theory and Perfect Graphs, Martin Charles Golumbic

General Information

 Lectures : Thu (15:00-16:55), Friday(14.00-15:55)
Room # : CS 107
Units : 3-1-0
Credits : 3
Contact : Room #322 (CSE), Phone 82358

Class attendance is mandatory!

Evaluation

 Midsem: 30
Endsem: 30
Class Test 1 (pre-midsem): 10
Class Test 2 (post-midsem): 10
Tutorial/Assignment : 12
Attendance : 8

Lectures

 Slides just contain very informal outlines of the topics; details will be discussed in the class.
1. Graph Fundamentals: Slides
2. Paths, Cycles, and Connectivity: Slides
3. Bipartite graph, Euler circuits: Slides
4. Graphical sequence : Slides
5. Trees: Slides