Skip to main navigationSkip to main content
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; the conditions under which a graph is planar; and the introductory elements of the theory of random graphs.

### Aims and Objectives

#### Module Aims

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.

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

TypeHours
Teaching48
Independent Study102
Total study time150

#### Resources & Reading list

Wilson RJ. Introduction to Graph Theory.

W.D.Wallis. A beginner's guide to graph theory.

Biggs NL, Lloyd EK & Wilson RJ (1736-1936). Graph Theory.

Biggs NS. Discrete Mathematics.

Bryant V. Aspects of Combinatorics.

Clark J & Holton DA. A First Look at Graph Theory.

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

### Linked modules

Prerequisites: MATH1048 AND MATH1049 AND (MATH1060 OR MATH1056)

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

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.

We use cookies to ensure that we give you the best experience on our website. If you continue without changing your settings, we will assume that you are happy to receive cookies on the University of Southampton website.

×