Description

This is a graduate level course that builds upon concepts presented in introductory undergraduate courses in Graph Theory. While the field of Graph Theory is rich and diverse, this course considers focusses on three selected topics, going into greater depth than is experienced in undergraduate courses. An emphasis is placed upon proofs and proof techniques which in turn provides preparation for future research and study.

The topics for the course typically include:

• Matchings: matchings, covers, the König-Egerváry theorem, Hall's theorem, Tutte's 1-factor theorem
• Connectivity: connectivity and edge-connectivity, Menger's theorem, Dirac's fan lemma, Mader's theorem for vertex-transitive graphs
• Network flows: networks, flows, cuts, the Ford-Fulkerson algorithm, Menger's theorem, circulations

Prerequisites

An introductory undergraduate course in Graph Theory
or permission from the instructor.

References

• J.A. Bondy and U.S.R. Murty. Graph theory. Springer, 2008.
• R. Diestel. Graph theory, third edition. Springer, 2005.
• D.B. West. Introduction to graph theory, second edition. Prentice-Hall, 2001.