Graph Theory module (MA41007)

Graph theory is an area of pure mathematics that can be applied to networks and structures. This module will introduce you to the key properties of graphs. You will use theory of graphs to solve real-world problems.

Physical structures often play a part in graph theory, and so this is a very visual subject, making it an ideal setting for you to develop your approach to understanding theoretical results.

You will learn how to use algorithms to enable computers to solve graph theory problems. You will also meet some famous problems from the history of mathematics along the way.

What you will learn

In this module, you will:

• understand what graphs are, basic properties of graphs, and special types of graphs
• learn the definitions of connectedness, and the theoretical results relating to the connectivity of graphs
• apply Eulerian and Hamiltonian graphs to real-world problems
• use calculations and theoretical results for tree graphs

By the end of this module, you will be able to:

• measure connectedness and prove connectivity results of graphs
• classify and identify graphs and circuits as Eulerian and/or Hamiltonian
• prove properties of trees and carry out relevant calculations with trees
• determine when graphs can be drawn with no edges crossing, both on a plane and on a torus
• colour graphs following the standard rules and theory of graph colouring

Assignments / assessment

• coursework (20%)
• final exam (80%)

Teaching methods / timetable

• one-hour lectures weekly
  • key points of the week's content will be discussed
  • lecture notes covering the full module content will be available before classes
  • video content on key concepts will also be available
  • in-class time will be prioritised for interactive discussion
• two hours of tutorials weekly
  • solve problems individually and in groups
  • support with difficulties will be provided by your lecturers and peers