Basics of Graph Theory (8 Weeks)
Basic definitions & isomorphism, walks, trails, paths, cycles, forests & trees, connected vs disconnected graphs, subgraphs, spanning subgraphs & spanning trees, bipartite graphs vs odd cycles (with proof), vertex colourings, Eulerian tours vs Hamiltonian cycles, characterisation of Eulerian graphs (with proof), vertex-connectivity & edge-connectivity, Menger’s Theorem (with proof), Matchings and Hall's Theorem. Planar graphs, Euler formula. Digraphs, DAGs, Tournaments - basics and properties.
Algebraic Structures (4 weeks)
Semigroups, Monoid and Groups, Rings, and Fields. Vector spaces, bases.
Basic Number Theory (2 Weeks)
Divisibility, GCD, Bezout’s Lemma, Properties of primes. Modular arithmetic,
Congruences, Chinese remainder theorem. Fermat's little theorem.
Text Books
1. Graph Theory by Bondy and Murty, Springer 2008.
2. Abstract Algebra, by I. N Herstein, 3rd edition, Prentice-Hall, 1996.
3. An Introduction to the Theory of Numbers, Ivan Niven, Herbert S. Zuckerman and Hugh Montgomery, 5th Edition, John Wiley & Sons, 1991.
Reference Books
1. Introduction to Graph Theory by Douglas B. West, Second Edition, Pearson, 2006.
2. Mathematics for Computer Science Eric Lehman, F Tom Leighton and Albert R Meyer -
link
3. Building blocks for TCS (Fleck) -
link
