LTCC Course: Graph Theory

General information about the LTCC course on Graph Theory

This is a course intended for first year research students in Mathematics, provided for the London Taught Course Centre (LTCC). See the LTCC website for full details of the objectives and activities of the LTCC, and of other available courses.

See here for general information about the course -- much of the information in the handout is repeated below.

Teacher responsible:
Peter Allen,
Department of Mathematics, LSE

Lectures:
13 January - 10 February 2020
in De Morgan House, London.

General description

Objectives

Our aims in this course are twofold. First, to discuss some of the major results of graph theory, and to provide an introduction to the language, methods and terminology of the subject. Second, to emphasise various approaches (algorithmic, probabilistic, etc) that have proved fruitful in modern graph theory: these modes of thinking about the subject have also proved successful in other areas of mathematics, and we hope that students will find the techniques learnt in this course to be useful in other areas of mathematics.

Reading material

Below is a collection of books, including some that can be accessed online. Any one of these textbooks should give sufficient reading material. The code before each book will be used in the table of contents below.

B&M: J.A. Bondy and U.S.R. Murty, Graph Theory. Springer (2008).
A thorough and well-written textbook covering most parts of modern graph theory. In many institutes you will be able to read this book online.
Long ago, Bondy and Murty wrote one of the classic textbooks on graph theory: Graph Theory with Applications. North Holland (1976). This book is out of print (and has been out of print for ages). But the full text is available online for personal use. You can download it from here.
Diestel: Reinhard Diestel, Graph Theory (1st, 2nd, 3rd, or 4th edition). Springer-Verlag (1997, 2000, 2005, 2010).
Although this book is still in print, the author has made sure that a restricted version is available online as well. See diestel-graph-theory.com/. All editions are suitable for this course. References in the notes will refer to the 4th edition (which is the same as the one you can download most parts of).
Bollobás: Béla Bollobás, Modern Graph Theory, Springer-Verlag (1998).
This is another classic textbook aimed at students at this level, and is suitable for the course.

Pre-requisites

Many people attending the course will have taken an introductory course in graph theory or discrete mathematics before, and we assume a certain amount of basic knowledge in graph theory.

Specifically, we expect students attending these lectures to be familiar with the following notions:
graphs; trees; paths; cycles; vertex degree; connectedness; bipartite graphs; complete graphs; subgraphs.

Those requiring a quick refresher are advised to look at the introductory chapter of any of the books listed above, before the course starts.

Contents and notes

Below is the rough schedule for this course, with notes. Some of these notes are from last year; they will be updated in due course. It is likely that there will be some small changes this year.

Week Topics Notes

Week 1 Graph Colouring
Notes and Exercises 1
Solutions to Exercises 1

Week 2 Graphs on Surfaces; Graph Minors
Notes and Exercises 2
Solutions to Exercises 2

Week 3 Algorithms and Complexity
Notes and Exercises 3
Solutions to Exercises 3

Week 4 Probabilistic Methods and Random Graphs
Notes and Exercises 4
Solutions to Exercises 4

Week 5 Ramsey Theory and Regularity
Notes and Exercises 5
Solutions to Exercises 5

Week	Topics	Notes
Week 1	Graph Colouring	Notes and Exercises 1 Solutions to Exercises 1
Week 2	Graphs on Surfaces; Graph Minors	Notes and Exercises 2 Solutions to Exercises 2
Week 3	Algorithms and Complexity	Notes and Exercises 3 Solutions to Exercises 3
Week 4	Probabilistic Methods and Random Graphs	Notes and Exercises 4 Solutions to Exercises 4
Week 5	Ramsey Theory and Regularity	Notes and Exercises 5 Solutions to Exercises 5

Examination questions

Here is the 2017 exam, with solutions.
And here is the 2018 exam, of course also with solutions.
And finally the 2019 exam, with solutions.