Graph Theory (Cambridge Part II 2016-17 Course)



Frankie Higgs


This course is an introduction to the theory of finite undirected graphs.

It touches on theorems from a lot of different areas:
1. Basic definitions, trees, bipartite graphs, planar graphs
2. Connectivity and matchings, Hall's marriage theorem
3. Extremal graph theory, Euler circuits and Hamilton cycles, Turán's theorem
4. Graph and edge colourings, 5-colour theorem and Kempe's "proof" of 4-colour theorem, graphs drawn on surfaces
5. Ramsey's theorem, bounds on Ramsey numbers, Erdős' lower bound
6. Random graph arguments, threshold properties
7. Adjacency matrix and algebraic results, strongly regular graphs

These cards contain definitions, statements and proofs of theorems from the course.

I wrote these only to aid with remembering facts for the exam - I've provided them here in the hope that they'll be helpful to someone taking an equivalent course in the same position.
They may be of interest to someone who isn't taking a similar course, but since I've not included any of the explanation or motivation that accompanied the theorems, you'll be better off learning the material first from a textbook.
I feel this is particularly true in this course - as the theorems themselves are very easy to understand (even if the proofs aren't) understanding the techniques and the ideas behind the proofs is more important than simply knowing the argument. Not to mention that the proofs take a long time to understand, so it will not be easy to learn them using these cards. Still, if you have to know them for an exam, these may be helpful.
For anyone interested in learning about graph theory, I found Bela Bollabás' book Modern Graph Theory to be a good introduction.

This may go without saying, but a fellow student has had a little trouble along these lines before: if you are taking a course in this subject, these notes are not a substitute for attending lectures.

A note on the cards: I found the LaTeX renderer used by Mnemosyne to be ugly and difficult to read, so the cards are in fact PNG images rendered from LaTeX. This does mean they are a pain to edit, and may not fit nicely on mobile screens. If anyone would like the source files to render themselves, email [email protected] and I will provide them.


Based on my lecture notes from the Cambridge University part II course "Graph Theory", lectured in Lent term 2017 by Prof. Imre Leader

As far as I can tell, this course has no official webpage, and no typed notes.
The cards here are adapted from what was said in lectures rather than any written resource.

Mnemosyne Compatibility: 

  • 2.1+

Card Set File: