Basic Concepts: Graphs and digraphs, incidence and adjacency matrices, isomorphism, the automorphism group;
Trees: Equivalent definitions of trees and forests, Cayleys formula, the Matrix-Tree theorem, minimum spanning trees;
Connectivity: Cut vertices, cut edges, bonds, the cycle space and the bond space, blocks, Menger's theorem;
Paths and Cycles: Euler tours, Hamilton paths and cycles, theorems of Dirac, Ore, Bondy and Chvatal, girth, circumference, the Chinese Postman Problem, the Travelling Salesman problem, diameter and maximum degree, shortest paths;
Matchings: Berge's Theorem, perfect matchings, Hall's theorem, Tutte's theorem, Konig's theorem, Petersen's theorem, algorithms for matching and weighted matching (in both bipartite and general graphs), factors of graphs (decompositions of the complete graph), Tutte's f-factor theorem;
Extremal problems: Independent sets and covering numbers, Turan's theorem, Ramsey theorems;
Colorings: Brook's theorem, the greedy algorithm, the Welsh-Powell bound, critical graphs, chromatic polynomials, girth and chromatic number, Vizing's theorem;
Graphs on surfaces: Planar graphs, duality, Euler's formula, Kuratowski's theorem, toroidal graphs, 2-cell embeddings, graphs on other surfaces;
Directed graphs: Tournaments, directed paths and cycles, connectivity and strongly connected digraphs, branchings;
Networks and flows: Flow cuts, Max flow min cut theorems, perfect square;
Selected topics: Dominating sets, the reconstruction problem, intersection graphs, perfect graphs, random graphs.
Tutorial-1 - August 12, 2022
Tutorial-2 - September 09, 2022
Tutorial-3 - September 16, 2022
Tutorial-4 - October 07, 2022
Homework-1- August 06, 2022
Homework-2- August 18, 2022
Homework-3- September 11, 2022
Homework-4- October 01, 2022
Two class tests will be conducted for this course.
Test 1 answers- September 09, 2022
Test 2- November 11, 2022
Mid-semester questions- September 27, 2022
End-semester questions- November 23, 2022
The term project topics are as follows
| Student name | Project Topic |
|---|---|
| Vytla Dinesh Chandra | TBD |
| Shubham Kumar | f-factors of a Graph |
| Esha Manideep Dinne | Chromatic Numbers and Graph Ramsey Theory |
| Shashwat Shukla | Properties of separability of graphs |
| Soumita Hait | Flows and Matchings |
| Dharavathu Sai Deepak Nayak | TBD |
| Pranav Rajput | Matrix tree theorems |
| Avyukt Aggarwal | Braess's paradox / Proof of Kurtowski's Theorem |
| Subham Ghosh | Planarity in graphs |
| Amaljith E.V | Open Problems and Conjectures In Graph Theory |
The mid term examination was conducted September 27, 2022 at 9 am in CSE 107.
The end term examination will be conducted at the end of November 2022.