• Definitions of basic numerical quantities of graphs, including diameter and radius, minimum and maximum degree, girth and circumference, chromatic number and chromatic index, clique number and independence number; other invariants may be included beyond these;
• Eulerian graphs, and necessary and sufficient conditions for a graph to be Eulerian;
• Hamiltonian graphs, and sufficient conditions for a graph to be Hamiltonian, including Ore’s Theorem;
• Trees, including Prufer sequences and Cayley’s theorem for the number of spanning trees of a complete graph;
• Planar graphs, including the statement, proof and applications of Euler’s formula; the statement (but not the proof) of Kuratowski’s theorem.
• Vertex colourings of graphs, including the greedy algorithm for producing a vertex colouring and the statement of Brooks’ theorem;
• Vertex colourings of planar graphs, including the statement and proof of the five colour theorem, and the statement of the four colour theorem;
• Edge colourings of graphs, including edge colourings of bipartite graphs, and the statements of Vizing’s theorem and Koenig’s theorem.
• Basic definitions and properties of random graphs; Erdos’s theorem on the existence of graphs with large girth and large chromatic number.
Learning and Teaching
Teaching and learning methods
Lectures, weekly tutorials, regular exercises, private study