MA 216: Introduction to Graph Theory

Credits: 3:0

Graphs, subgraphs, Eulerian tours, trees, matrix tree theory and Cayley’s formula, connectedness and Menger’s theorem, planarity and Kuratowski’s theorem, chromatic number and chromatic polynomial, Tutte polynomial, the five-colour theorem, matchings, Hall’s theorem, Tutte’s theorem, perfect matchings and Kasteleyn’s theorem, the probabilistic method, basics of algebraic graph theory

No prerequisites are expected, but we will assume a familiarity with linear algebra.

Suggested books and references:

  1. Adrian Bondy and U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics, 244. Springer, New York, 2008, ISBN: 978-1846289699.
  2. Reinhard Diestel, Graph theory (Third edition), Graduate Texts in Mathematics, 173. Springer-Verlag, Berlin, 2005. ISBN: 978-3540261827.
  3. Douglas B. West, Introduction to graph theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996. ISBN: 0-13-227828-6.

All Courses

Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 04 Aug 2020