Synopsis for C11.1a: Graph Theory

Level: M-level Method of Assessment: Written examination.
Weight: Half-unit (OSS paper code 2A85).

Recommended Prerequisites

None

Overview

Graphs are among the simplest mathematical structures, but nevertheless have a very rich and well-developed structural theory. Graph Theory is an important area of mathematics, and also has many applications in other fields such as computer science.

The main aim of the course is to introduce the analysis of discrete structures, and particularly the use of extremal methods.

Learning Outcomes

The student will have developed an appreciation of extremal methods in the analysis and understanding of graphical structures.

Synopsis

Introduction. Trees. Euler circuits. Planar graphs.
Matchings and Hall's Theorem. Connectivity and Menger's Theorem.
Extremal problems. Long paths and cycles. Turán's Theorem. Erd\H os–Stone Theorem.
Graph colouring. The Theorem of Brooks. The chromatic polynomial.
Ramsey's Theorem.
Szemerédi's Regularity Lemma.

1. B. Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184 (Springer-Verlag, 1998)

Further Reading

1. J. A. Bondy and U. S. R. Murty, Graph Theory: An Advanced Course, Graduate Texts in Mathematics 244 (Springer–Verlag, 2007).
2. R. Diestel, Graph Theory, Graduate Texts in Mathematics 173 (third edition, Springer-Verlag, 2005).
3. D. West, Introduction to Graph Theory (second edition, Prentice–Hall, 2001).