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.
Prerequisites:
- Some knowledge of group theory is needed for part of the course.
- Students in this module are assumed to be familiar with the following topics from the 3rd year module 3DM (Discrete Mathematics):
- Basics: Graphs and digraphs, degree, isomorphism, operations on graphs,
- Distance in graphs,
- Basic graph structures: bipartite graphs, cut-vertices and bridges,
- Trees.
The above material can be found in this document.