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 (weeks 2, 4, 5) and Leo Versteegen (weeks 1, 3),
Department of Mathematics, LSE
Lectures:
17 February - 17 March 2025
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.
This course is basic in the sense that there are very few prerequisites and these are covered by most undergraduate degree programmes. However, we deliberately aim
not
to cover too much material that is in most undergraduate or masters courses. We will also proceed at a fairly high pace: there will be comprehensive notes
with all the details. More or less, you are supposed to come out of each lecture with
a rough idea of what techniques exist and the high points of how they work, with notes to help you find the details again
if you discover you need similar ideas in future. The aim is not that you should be able to reconstruct the proofs on the spot afterwards.
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 should look at the introductory PDF which contains a list of recommended books.
Contents and notes
Below is the rough schedule for this course, with notes which will appear as the course progresses.
Copyright © Jan van den Heuvel & London School of Economics and
Political Science 2008 - 2016, minor hacks due to Peter Allen, 2025