Target audience:
ECE/CSE/Math undergrads (for the 300 level)
Postgraduate students from ECE/CSE (with theoretical inclination), and Math postgraduate students (for the 500 level).
[This is a theoretical course, and the rigour will not be diluted under any circumstance. ]
Course description: This course is aimed at giving students an introduction to the theory of graphs. The course will introduce concepts that are widely used such as matchings, colorings, etc., and study relations between various graph parameters such as matching number, chromatic number, clique number, etc. The emphasis will be on common proof techniques, and applying them to prove properties of graphs in general and for specific families of graphs.
Course objectives/Learning outcomes:
Know elementary structural properties and be able to evaluate them for some simple graph classes.
Know about fundamental graph parameters and be able to calculate them for graph classes.
Know about connectivity, matchings, cuts and flows, coloring, planarity.
Write simple proofs based on the properties of the graphs and standard theorems.
Course notes: Find here.
Assignments and examinations:
Assignment 1 (2025)
Assignment 2 (2025)
Quiz 1 (2025)
Quiz 2 (2025)
Quiz 3 (2025)
Quiz 4 (2025)
Midterm (2025)
Final Examination (2025)
I would like to thank Farhan Ali, my TA for the 2025 edition of this course, for significantly contributing towards the questions for evaluations (the 2025 edition) as well as practice/tutorials. He is also the brain behind the graphic themes of the various 2025 papers.