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