MATH3033 Graph Theory
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; the conditions under which a graph is planar; and the introductory elements of the theory of random graphs.
Aims and Objectives
The primary aim of this module is to provide the interested student with an overview of the basics of graph theory. These basics include numerical graph invariants and properties of graphs, and constructions of graphs. We will explore these invariants, properties and constructions by considering them for several example families of graphs. We will also consider how these invariants, properties and constructions arise outside of the strict confines of graph theory, either in other parts of mathematics or in the world at large.
Having successfully completed this module you will be able to:
- Be able to state the definitions of numerical invariants associated to graphs as described in the syllabus; to use these definitions in proofs; and to calculate these invariants for specific examples and classes of graphs
- Be able to state and apply the definitions of and the fundamental results describing the behavior of graph properties such as being connected, being bipartite, being planar, being Eulerian or Hamiltonian; and determine whether these properties hold for specific examples and classes of graphs
• 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, connectivity and edge connectivity, Cheeger constant; • 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 the number of spanning trees of a connected graph, 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; the genus of a graph and the statement of Ringel-Young’s theorem. • Vertex colourings of graphs, including the greedy algorithm for producing a vertex coloring 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, bi-weekly tutorials, regular exercises, private study
|Total study time||150|
Resources & Reading list
W.D.Wallis. A beginner's guide to graph theory.
Clark J & Holton DA. A First Look at Graph Theory.
Biggs NS. Discrete Mathematics.
Biggs NL, Lloyd EK & Wilson RJ (1736-1936). Graph Theory.
Bryant V. Aspects of Combinatorics.
Wilson RJ. Introduction to Graph Theory.
Purpose of the Assessment Examination – To allow students to demonstrate that they have understood the material, and that they can carry out basic calculations and construct proofs correctly. Coursework (in-class tests) – To provide students with feedback on their progress at understanding the material during the course of the module Feedback Examination – Students will be emailed general comments on the performance of the class as a whole together with solutions to the examination, within a few weeks of the examination, in line with Mathematical Sciences and University feedback policies. Coursework – The tests are multiple choice; they will be marked and made available for the students to see within 1 week of the test date; in addition, full solutions to the tests will be made available on Blackboard. In addition, the tests will be scheduled so that part of one of the bi-weekly tutorial sessions can be used to provide additional feedback on common issues arising from the tests.
|Exam (120 minutes)||80%|
|In-class Test (40 minutes)||10%|
|In-class Test (40 minutes)||10%|
Repeat type: Internal & External
Prerequisites: MATH1049 and MATH1051 (or MATH1049) and MATH1056
Costs associated with this module
Students are responsible for meeting the cost of essential textbooks, and of producing such essays, assignments, laboratory reports and dissertations as are required to fulfil the academic requirements for each programme of study.
In addition to this, students registered for this module typically also have to pay for:
Books and Stationery equipment
Course texts are available for check out from the University Library and there are no additional compulsory costs associated with the module.
Please also ensure you read the section on additional costs in the University’s Fees, Charges and Expenses Regulations in the University Calendar available at www.calendar.soton.ac.uk.