Synopsis for B11b: Graph Theory

Level: H-level Method of Assessment: Written examination.
Weight: Half-unit (OSS paper code tbc).
Recommended Prerequisites: None

Overview

Graphs (abstract networks) are among the simplest mathematical structures, but nevertheless have a very rich and well-developed structural theory. Since graphs arise naturally in many contexts within and outside mathematics, 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 fundamental ideas of Graph Theory, and some of the basic techniques of combinatorics.

Learning Outcomes

The student will have developed a basic understanding of the properties of graphs, and an appreciation of the combinatorial methods used to analyze discrete structures.

Synopsis

Introduction: basic definitions and examples. Trees and their characterization. Euler circuits; long paths and cycles. Vertex colourings: Brooks’ theorem, chromatic polynomial. Edge colourings: Vizing's theorem. Planar graphs, including Euler’s formula, dual graphs. Maximum flow - minimum cut theorem: applications including Menger's theorem and Hall's theorem. Tutte's theorem on matchings. Extremal Problems: Turan's theorem, Zarankiewicz problem, Erdos-Stone theorem.

Reading

B. Bollobas, Modern Graph Theory, Graduate Texts in Mathematics 184 (Springer-Verlag, 1998)

Further Reading

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