Notes

This page contains links to the lecture notes for the course.

Lecture notes as a pdf

Lecture notes from a previous year. These are a bit skeletal, and do not match exactly what we cover, but they’re very close and you may find them useful.

Each day of lecture will have its own page. This will contain brief notes on the material covered and links to any slides I used in lecture.

Each lecture will have have a comment thread to ask questions and further discuss the material.

• Lecture 1: Introduction, Euler’s Handshaking Lemma

• Lecture 2: Instant Insanity, Isomorphisms

• Lecture 3: Connectedness. Walks, trails and paths.

• Lecture 4: Bridges of Konigsberg

• Lecture 5: Hamiltonian cycles

• Lecture 6: Trees

• The Lost Lecture 7: Leaves, chemistry, spanning trees

• Lecture 8: Prüfer code

• Lecture 9: Spanning Trees, Kruskal’s algorithm

• Lecture 10: Kruskal proof, Traveling Salesman

• Lecture 11: Routing algorithmns – Dijkstra’s and A*

• Lecture 12: Scheduling and longest paths

• Lecture 13: Planar Graphs

• Lecture 14: Kuratowski’s theorem; graphs on the torus and Mobius band

• Lecture 15: Unorientable surfaces; classification of surfaces, dual graphs

• Lecture 16: Euler’s Theorem and applications

• Lecture 17: Chromatic Number

• Lecture 18: Chromatic Index, Intro to Chromatic polynomial

• Lecture 19: Chromatic Polynomial

• Lecture 20: Catch-up, 5-Colour Theorem