Course Information Undergraduate prospectus

Graph Theory and Applications

Course summary

Course code: MATH1135
Level: 6
Credits: 15
School: Architecture, Computing and Hums
Department: Mathematical Sciences
Course Coordinator(s): Anthony Mann


Pre and co requisites

Linear Algebra and Applications.


Whereas twenty years ago the major industrial uses of mathematics related to continuous mathematics such as differential equations, in the twenty-first century there is a greater demand for discrete mathematics and combinatorics. This course aims to enhance graduates' employability by giving students experience of the theory and applications of discrete mathematics and to show how it is used in careers in mathematics.

Learning outcomes

On successful completion of this course a student will be able to:

1. Solve problems by applying graph-theoretic results and algorithms.
2. Identify methods of discrete mathematics that are appropriate for industrial and business problems.

Indicative content

Introduction to graphs and digraphs, walks, paths, trails and cycles. Eulerian and Hamiltonian graphs.
Connectivity - Whitney's theorem and Menger's theorem.
Planarity - Kuratowski's theorem and Euler's theorem.
Colourability - 5-colour theorem, 4-colour theorem.
Algorithms - Greedy algorithm, shortest path algorithms, Fleury's algorithm.
NP completeness.
Applications in computing, engineering, finance, mathematical biology, social networks.

Teaching and learning activity

Lectures, workshops, tutorials, directed guided learning, student investigation.


Summative assessment:
Coursework -50%
Investigative coursework covering primarily learning outcome 2.

Examination - 50%
Three-hour unseen examination covering primarily learning outcome 1.

Formative assessment: weekly tutorial exercises