module specification

MA4056 - Graph Theory (2023/24)

Module specification Module approved to run in 2023/24
Module title Graph Theory
Module level Certificate (04)
Credit rating for module 15
School School of Computing and Digital Media
Total study hours 150

 105 hours Guided independent study 45 hours Scheduled learning & teaching activities
Assessment components
Type Weighting Qualifying mark Description
In-Course Test 20%   Test
Unseen Examination 80%   Unseen Exam
Running in 2023/24

(Please note that module timeslots are subject to change)
Period Campus Day Time Module Leader
Spring semester North Friday Afternoon

Module summary

In this module, we introduce the basic concepts of graph theory, focusing 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.

None.

Syllabus

• Definitions, adjacency and incidence matrices.

• Particular graphs, graphic sequences, walks, paths, trails, cycles.

• Disconnecting sets, separating sets, edge-connectivity, vertex connectivity.

• Counting walks, Eulerian graphs, Hamiltonian graphs.

• Planar graphs - Euler’s formula, Kuratowski’s theorem, dual graphs.

• Vertex colourings, Chromatic number and Chromatic polynomials.

Balance of independent study and scheduled teaching activity

This module will be delivered through a mixture of lectures and tutorials. The lectures will develop theory, explain the methods and techniques and demonstrate them by going through examples. The tutorials will provide students with the opportunity of reviewing their lecture notes and working through the problems designed for their practice, which will underpin the skills and techniques demonstrated in the lectures. Students will be encouraged to construct valid and precise mathematical arguments and will be expected to produce solutions using appropriate notational and stylistic conventions. Self-study exercises will enable students to monitor their own progress.

A set of lecture notes will be provided to students and answers for exercise questions will be put on the VLE.

Blended learning is incorporated by using online resources as a medium for communication (both peer and tutor-led) and will also provide additional materials to stimulate the student interest and broaden their horizons.

Learning outcomes

After successful completion of this module students should:

LO1: Be able to represent graphs in different forms and identify the main properties of given graphs and be able to interpret and evaluate the outcomes of algorithms.

LO2: Be able to count walks, trails, paths in a given graph and determine whether graphs are Eulerian/Hamiltonian etc.

LO3: Be able to apply Euler’s formula and related results to determine whether a graph is planar or not.

LO4: Be able to determine chromatic polynomial and chromatic number of a given graph.

Assessment strategy

The assessment for this module consists of a test and an exam.

There will be a progression test covering LO3, LO4 which will give students opportunity to demonstrate their understanding of selection of topics.

The final assessment will be an exam where students will be tested on LO4.

Bibliography

Core Text:

R.J.Wilson(1996), Introduction to Graph Theory (4-th edition) Longman