1st Semester
20 credits / 30 lectures
Graph Theory is the mathematics of networks: collections of things (which we call vertices or nodes or points), between some of which are connections (edges). The World Wide Web is a graph. So are the streets of a city, the complex web of interactions that constitutes human society, power stations and the connections between them, and Friends on Facebook. That having been said, this module deals with graphs as abstract mathematical structures and leaves you to pick up the applications on your own. Most of our time is spent covering various theorems and proofs. Possible topics covered include the following:
- Connectivity, vertex and edge cuts, Menger’s Theorem.
- Planar graphs, Kuratowski’s Theorem, the Four and Five Colour Theorems.
- Vertex colouring, Brooks’ Theorem.
- Eulerian and Hamiltonian graphs.
- Graphs and groups, permutation groups and the Cauchy-Frobenius-Burnside Theorem.
- Other topics to be decided.