B8.5 Graph Theory - Material for the year 2020-2021

We have updated our Undergraduate exams guidance in preparation for the Trinity Term examinations.

Please see our new webpages dedicated to TT exams.

Prof. Paul Balister
General Prerequisites: 

Part A Graph Theory is recommended.

Course Term: 
Course Lecture Information: 

16 lectures

Course Weight: 
1.00 unit(s)
Course Level: 

Assessment type:

Course 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.

Course 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, Erdős-Stone theorem.

Reading List: 
  1. B. Bollobas, 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).