• Instructor : M. Rajesh Kannan
• Instructor's mail id : rajeshkannan@math.iith.ac.in
• Class Schedule: Monday - 11 am - 11.55 am, Wednesday - 10 am - 10.55 am, Thursday 9 am - 9.55 am.
• Venue: A 117
• Office hours: By appointment (C-213(G)).

Topics covered

• Basics of graphs, isomorphism, trees, Minimum spanning tree, Kruskal's algorithm.
• Counting spanning trees, Prufer sequence, Cayley's formula, Matrix-tree theorem (without proof).
• Mantel's theorem. Bipartite graphs, Matching, Hall's theorem, System of distinct representatives.
• Eulerian graphs, Decompositions, Graham and Pollak theorem, Veblen's theorem.
• Hamiltonian graphs, Ore's theorem.
• Planer graphs, Euler's formula and its applications.
• Chromatic number, Five color theorem.
• Basic Counting: sum rule, product rule and inclusion-exclusion principle.
• Pigeon hole principle, generalized pigeon hole principle and its applications.
• Permutation and Combinations. Permutation and combinations with repetitions, binomial and multinomial coefficients.
• Weak compositions, compositions, set partitions, Stirling numbers, Bell numbers. Integer partition, Ferrer's shape, conjugate partitions. Catalan numbers.
• Recurrence relations. Solving linear recurrence relations with constant coefficients.
• Ordinary generating functions, exponential generating functions. Solving recurrence relations using generating functions.