MTL768/MTL7768: Graph Theory
Monsoon semester, 2026-27
Lectures by:
Ashutosh Rai for the first half, by Prof. Dalu Jacob for the second half.
Time of the class:
Tuesdays and Fridays 3:30pm to 4:50pm.
Office hours:
by email appointment.
Teaching assistants:
Sonam Gariya : maz238700@iitd.ac.in
Syllabus: We will roughly cover the following topics: Introduction to Graphs: Definition and basic concepts; Trees:
characterizations, counting of minimum spanning tree; Paths and
Distance in Graphs: Basic Definitions, center and median of a graph, activity digraph and critical path; Eulerian Graphs: Definition and
Characterization; Hamiltonian Graphs: Necessary and sufficient
conditions, Planar Graphs: properties, dual, genus of a graph; Graph
Coloring: vertex coloring, chromatic polynomials, edge coloring, planar graph coloring; Matching and Factorizations: maximum matching
in bipartite graphs, maximum matching in general graphs, Hall’s
marriage theorem, factorization; Networks: The Max-flow min-cut
theorem, connectivity and edge connectivity, Menger’s theorem; Graph
and Matrices.
Course Material:
We will follow the book "Introduction to Graph Theory" by Douglas West [DW], for which a low price edition is available in India.
I might sometimes refer to some other material, in which case I will mention that. Students can also refer to the following book if they are interested.
- Graph Theory (Springer) by Reinhard Diestel [RD]
Credits:
The course will be evaluated on a 100 point scale.
There will be 2 quizzes of 15 points each.
The minor and major will be worth 30 and 35 points respectively.
To audit pass the course, you need to have at least 40 points.
5 points will be there attendance. For at least 85 percent attendance you get 5 points, for at least 80 but less than 85, you get 2 points, and no attendance points for less than 80 percent attendance. Attendance will be done through rollcall.
Anyone found using unfair means for attendance will lose all the attendance marks, and repeated violations can face further consequence, including, but not limited to, lowering of a grade or failing the course.
There will be only one make-up exam to make up for missed quizzes or minor. One can appear in at most one make-up exam, either the re-quiz or the re-minor, both of which will be conducted before the major, and would contain the full syllabus.
Attendance of 75% is required to get credits for the course as per institute rules.
Lectures and References:
Lecture 1: Introduction to graphs: definition, applications. Reference: [DW] 1.1.
Lecture 2: Representation of graphs, ismorphisms, paths, trails. Reference: [DW] 1.1, 1.2.
Lecture 3: Induced subgraphs, Bipartite graphs: Konig's Theorem, Cliques as union of bipartite graphs, Degrees and Handshaking Lemma. Reference: [DW] 1.2, 1.3.
Lecture 4: Degree sequences and graphic sequences, Eularian graphs and characterization . Reference: [DW] 1.3, 1.2.
Lecture 5: Trees: definition and characterization, spanning trees, tree as a subgraph. Reference: [DW] 2.1.
Lecture 6: Enumerating trees: Prufer codes. Reference: [DW] 2.2.
Lecture 7: Counting spanning trees: by recursion and Matrix-Tree Theorem, Shortest path: Dijkstra's, Minimum Spanning Trees: Prim's and Kruskal's, BFS/DFS. Reference: [DW] 2.2, 2.3.
Lecture 8: Matchings, Maximal and Maximum matchings, M-alternating and M-augmenting paths, Hall's Theorem. Reference: [DW] 3.1.
Lecture 9: Konig's Theorem. Reference: [DW] 3.1.
Lecture 10: Tutte's Theorem. Reference: [DW] 3.3.
Lecture 11: Relation between parameters: Sizes of Mathchings, Edge Covers, Vertex Covers, Independednt Sets. Reference: [DW] 3.2.
Lecture 12: Connectivity: Cuts, Vertex- and Edge-connectivity, relationship to minimum degree, examples. Reference: [DW] 3.1.
Lecture 13: Connectivity inequalities, Hahary Graphs, Vertex- and Edge-connectivity of 3-regular grapgs, relationship between minimum degree and size of a minimum cut and partition induced by it. Reference: [DW] 3.1.
| |