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:
14 January  11 February 2019
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 wellwritten 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).
SpringerVerlag (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 diestelgraphtheory.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, SpringerVerlag (1998).
This is another classic textbook aimed at students at this level, and is
suitable for the course.
Prerequisites
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 and exercise solutions to appear during the course.
Week 
Topics 
Notes 
Week 1 
Graph Colouring

Notes
and Exercises 1

Week 2 
Graphs on Surfaces; Graph Minors


Week 3 
Algorithms and Complexity


Week 4 
Probabilistic Methods and Random Graphs


Week 5 
Ramsey Theory and Regularity


Examination questions
Here is the 2018 exam with solutions.
Here is the 2017 exam with solutions.
Copyright © Jan van den Heuvel & London School of Economics and
Political Science 2008  2016, minor hacks due to Peter Allen, 2017