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.
The following handout summarises some general information about the course – much of the information in this handout is repeated below.
Introduction: Notes 0 - Introduction
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 the skills learnt in this course should be transferable to other areas of mathematics.
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.
Below is a collection of books, including some that can be accessed online. Any one of the first three textbooks should give sufficient background reading material; the final textbook is relevant for the final two lectures.
Diestel – Reinhard Diestel, Graph Theory (1st-5th edition). Springer (1997-2016).
See diestel-graph-theory.com.
Although this book is still in print, the author has made sure that it is available in several versions online as well. The free downloadable version has low quality, but is perfectly readable.
Most editions are suitable for this course. References in the notes will refer to the 5th edition (which is the same as the one you can download for free (chapter by chapter)).
Bondy & Murty – J.A. Bondy and U.S.R. Murty Graph Theory. Springer (2008).
See link.springer.com/book/9781846289699
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.
Bollobás – Béla Bollobás, Modern Graph Theory (1st-3rd edition). Springer (1998-2002).
See link.springer.com/book/10.1007/978-1-4612-0619-4.
This is another classic textbook aimed at students at this level, and is suitable for the course.
Alon & Spencer – Noga Alon and Joel H. Spencer, The Probabilistic Method (1st–4th edition). Wiley (1991–2016).
See www.wiley.com/en-gb/The+Probabilistic+Method%2C+4th+Edition-p-9781119061953
A great, clearly written, and well-motivated book with applications of probability in combinatorics. Many exercises. You can download the 3rd edition via math.bme.hu/~gabor/oktatas/SztoM/AlonSpencer.ProbMethod3ed.pdf
Here the lecture notes (with exercises) accompanying the lectures will be published throughout the course. We encourage all students to attempt the exercises after the corresponding lectures.
Introduction: Notes 0 - Introduction
Week 1: Graph Colouring: Notes and Exercises for Week 1
Week 2: Graphs on Surfaces; Graph Minors: Notes and Exercises for Week 2 (update 14/11/22; correction in Thm. 5)
Week 3: Algorithms and Complexity: Notes and Exercises for Week 3 (update 21/11/22; some corrections at top of page 2)
Week 4: Probabilistic Methods and Random Graphs: Notes and Exercises for Week 4 (update 28/11/22)
Week 5: Ramsey Theory and Regularity Notes and Exercises for Week 5 (update 29/11/22)
More on the Regularity Lemma (see Chapters 1 and 3): Andrew Treglown, The Regularity Lemma and applications to packings in graphs.
2022 exam and solutions (The paper says “2021 Examination”, but this really is last year’s exam.)
Copyright © Discrete Mathematics group, London School of Economics and Political Science 2007-2022