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

**Teachers responsible:**

Julia Böttcher and
Jan van den
Heuvel,

Department of Mathematics, LSE

**Lectures:**

5 October - 2 November 2015

in De Morgan House, London.

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

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.

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 (updated 2 Nov 2015) Solutions to Exercises 4 |

Week 5 | Ramsey Theory and Regularity |
Notes
and Exercises 5 (updated 2 Nov 2015) Solutions to Exercises 5 |

Here is the 2013
exam, with solutions.

And here is the 2014
exam, of course also with solutions.

Last modified: Wed Apr 6 08:38:32 BST 2016