Graph Theory module (MA41007)

On this page
Credits

15

Module code

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.

Prerequisites

Students taking this module must have achieved a pass mark in the module MA22001 or equivalent.

Indicative Content

  • Introduction to Graph Theory
    • Fundamental definitions of graph theory
    • Introduction to some special types of graphs
    • Degree sequences and corresponding graphs
  • Connectedness
    • 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
  • Trees 
    • 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%).

Credit Rating

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.