The University of Southampton
Courses

# MATH3033 Graph Theory

## 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.

### Aims and Objectives

#### Learning Outcomes

##### Learning Outcomes

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, as well as for graph constructions
• Be able to state and apply the definitions of and the fundamental results describing the behaviour of graph properties as described in the syllabus; and determine whether these properties hold for specific examples and classes of graphs, as well as for graph constructions

### Syllabus

• 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

TypeHours
Teaching48
Independent Study102
Total study time150

### Assessment

#### Assessment Strategy

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 in the same style as the final examination; they will be marked and made available for the students within 1 week of the test date, and full solutions to the tests will be made available on Blackboard. In addition, the weekly tutorial session following each test will be used to provide additional feedback on common issues arising from the tests.

#### Summative

MethodPercentage contribution
Exam  (120 minutes) 80%
In-class Test  (40 minutes) 10%
In-class Test  (40 minutes) 10%

#### Referral

MethodPercentage contribution
Exam 100%

#### Repeat Information

Repeat type: Internal & External

Prerequisites: MATH1048 AND MATH1049 AND MATH1060

### Costs

#### 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

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.