Graph Theory module (MA41007)
About the module
The aim of this module is to introduce Level 4 students to graph theory including theoretical work and the implementation of algorithms. This module may optionally be taken in combination with other modules by students taking the BSc or MMath in Mathematics or any of the other Mathematics combined degrees. If you have questions about this module or the possible combinations, please contact your Advisor of Studies.
Students taking this module must have achieved a pass mark in the module MA22001 or equivalent.
- Introduction to Graph Theory
- Fundamental definitions of graph theory
- Introduction to some special types of graphs
- Degree sequences and corresponding graphs
- Sufficient conditions to ensure connectedness
- Connectivity and edge connectivity
- Tarry’s algorithm.
- Eulerian and Hamiltonian Graphs
- Necessary and sufficient conditions for graphs to be Eulerian
- Fleury’s algorithm
- Necessary conditions for graphs to be Hamiltonian
- Properties of trees
- Spanning trees and labelled spanning trees
- Finding minimum-weight spanning trees
- Planar and Non-planar Graphs
- Necessary conditions for graphs to be Planar
- Toroidal graphs
- Genus of graphs
- Graph Colourings
- Vertex and edge colourings Chromatic polynomials
- The 4-colour theorem
Delivery and Assessment
The module is delivered in the form of lectures and workshops/tutorials and assessed via an exam (80%) and coursework (20%).
This module is a Scottish Higher Education Level 4 or SCQF level 10 module and is rated as 15 SCOTCAT credits or 7.5 ECTS credits.