Course Instructor: Dalu Jacob, Office: 527 A, Academic complex West (99B), dalujacob@math.iitd.ac.in
Time and Venue: Mon, Thu 3:30-4:50 pm , LH 308
Teaching Assistants:
Soumyasree Rana, maz218122@maths.iitd.ac.in
Subhasmita Joshi, maz238454@maths.iitd.ac.in
Syllabus:
Introduction to graphs; Trees and distance: properties, spanning trees and enumeration etc.; Matchings and covers; Connectivity: cuts, vertex/edge connectivity, Menger's theorem, etc.; Network flow; Graph coloring: vertex coloring, Brooks' theorem, color critical graphs etc.; Planar graphs: Embeddings, Euler Formula, Kuratowski's theorem, coloring of planar graphs etc. ; Line graphs and edge coloring; Hamiltonian cycles; Special classes of graphs: chordal graphs, interval graphs, perfect graphs etc.
Evaluation Plan
2 Quizzes (best of three)+ 1 Assignment: 30 marks (10 marks each)
Minor: 30 marks
Major: 40 marks
To audit pass the course, you need to have at least 35 marks, at least 25 of which should come from minor and major.
Remark: No re-quizzes will be conducted
Attendance Policy: Attendance in the lecture class is to be maintained as per the Institute rules.
References
Primary reference: Introduction To Graph Theory, D. B. West [link]
Additional references:
Graph theory, Reinhard Diestel [link]
Graph theory with Applications, J. A. Bondy and U. S. R. Murty [link]
Topics covered
Lecture-1: Introduction to graphs, notations and Preliminaries, Graphs as models, and some applications of graph-theoretic problems (Reference: Chapter 1, Section 1.1, D. B. West).
Lecture-2: Adjacency matrix and Incidence matrix, Isomorphism and non-isomorphisms of graphs, Petersen graph and its properties, Walks, trails, paths and their structural properties (Reference: Chapter 1, Section 1.1, 1.2, D. B. West).
Lecture-3: Characterization of bipartite graphs, the union of graphs, covering complete graphs using bipartite graphs, Eulerian graphs (Reference: Chapter 1, Section 1.2, D. B. West).
Lecture-4: Characterization of Eulerian graphs, Vertex degrees and counting: Handshake lemma, its corollaries, degree sequence and graphic sequence, Havel and Hakimi theorem for testing a sequence is graphic (Reference: Chapter 1, Section 1.2, 1.3, D. B. West).
Lecture-5: Trees: Properties, Characterizations and their Consequences (Reference: Chapter 2, Section 2.1, D. B. West).
Lecture-6: Distances in trees and graphs: diameter, eccentricity, radius, etc. center of a tree, enumeration of trees, Algorithm for finding Prufer code of a tree (Reference: Chapter 2, Section 2.1, 2.2, D. B. West).
Lecture-7: Enumeration of trees: Cayley's formula; proof and its consequences, edge contraction, recurrence relation for enumerating all the spanning trees of a graph (Reference: Chapter 2, Section 2.2, D. B. West).
Lecture-8: Matrix tree theorem (without proof), Matchings in graphs, some examples, perfect matchings, alternating paths and augmenting paths (Reference: Chapter 3, Section 3.1, D. B. West).
Lecture-9: Hall's marriage theorem, Min-Max theorems (relation between maximum matching and minimum vertex cover, Konig's theorem for matchings in bipartite graphs, Dual optimization problems, Independent sets and edge cover (Reference: Chapter 3, Section 3.1, D. B. West).
Lecture-10: Relationship between matching, independent sets, vertex/edge cover parameters, Application of Hall's theorem, Stable matchings, Gale-Shapley algorithm
(Reference: Chapter 3, Section 3.2, D. B. West).
Lecture-11: Maximum matching in general graphs: Tutte's 1-factor theorem (Reference: Chapter 3, Section 3.3, D. B. West).
Lecture-12: Cut-vertex, cut-edge, vertex/edge connectivity, Examples, Relationship between the vertex/edge connectivity parameters (Reference: Chapter 4, Section 4.1, D. B. West).
Lecture-13: Graphs having the same vertex connectivity and edge connectivity, block graphs, block decomposition, Whitney's theorem for 2-connectedness (Reference: Chapter 4, Section 4.2, D. B. West).
Lecture-14: Sub-division of graphs, Ear Decomposition, Menger's theorem (Reference: Chapter 4, Section 4.2, D. B. West).
Lecture-15: Graph coloring and its applications, Greedy coloring, Coloring interval graphs, Mycielski Construction (Reference: Chapter 5, Section 5.1, 5.2, D. B. West).
Lecture-16: Brook's theorem, Gallai-Roy-Vitaver theorem(Reference: Chapter 5, Section 5.1 D. B. West).
Lecture-17: Extremal problems and Turan's theorem, Color critical graphs (Reference: Chapter 5, Section 5.2, D. B. West).
Lecture-18: Connectivity of Color critical graphs (Reference: Chapter 5, Section 5.2, D. B. West).
Lecture-19,20: Chordal graphs, simplicial elimination ordering, perfect graphs, line graphs (Reference: Chapter 5, Section 5.3, D. B. West).
Lecture-21: Edge coloring: in bipartite graphs, Vizing's theorem (Reference: Chapter 7, Section 7.1, D. B. West).
Lecture-22: Planar graphs: Motivation, Dual graphs, Outer planar graphs, (Reference: Chapter 6, Section 6.1, D. B. West).
Lecture-23: Euler's formula and its applications, Characterization of planar graphs: Preparation for the proof of Kuratowski's theorem (Reference: Chapter 6, Section 6.2, D. B. West).
Lecture-24,25: Final proof of Kuratowski's theorem, Coloring of Planar graphs: Five color theorem for planar graphs (Reference: Chapter 6, Section 6.3, D. B. West).