Module overview
Graph theory was born in 1736 with Euler’s solution of the Königsberg bridge problem, which asked whether it was possible to plan a walk over the seven bridges of the town without re-tracing one’s steps. Euler realised that the problem could be rephrased in terms of a graph whose vertices corresponded to the four regions of the city, and whose edges corresponded to the seven bridges each joining a pair of the regions.
With this rephrasing, we can view this problem of walking through Königsberg as a (significantly more tractable) problem of navigation in the corresponding diagram (or graph), which is straightforward to resolve.
Graph theory is a stand-alone branch of mathematics that has links across the mathematical spectrum, from parts of pure mathematics such as abstract algebra and topology, to parts of mathematics focusing on applications such as operational research and computation, through to other areas of science such as chemistry, biology and electronics.
In this module, we introduce the basic concepts of graph theory, focusing primarily on finite graphs. These include numerical invariants of graphs and methods for calculating them; how to navigate through graphs (including the method that lies behind the resolution of the Königsberg problem discussed above); vertex and edge colourings of graphs and other numerical invariants of graphs; the conditions under which a graph is planar; and the introductory elements of the theory of random graphs.
Linked modules
Prerequisites: MATH1048