School of Mathematics and Statistics

Home | About the school | Contact | Courses | Research | Personnel list

Courses in
and Statistics

Level 1 Modules

Level 2 Modules

Level 3 Modules

Level 4 Modules

Level 5 Modules


2013/2014 Sem. 1

2013/2014 Sem. 2



To introduce students to graph theory, as a tool for solving problems in mathematics and elsewhere, but also as an attractive study in its own right.


By the end of the course students should know about topics such as the following and be able to solve problems in these areas.

- Applications of graph theory: Königsberg bridges, Knight's tours, puzzles, saturated hydrocarbons, network problems.

- Basic theory: isomorphism and degree.

- Eulerian graphs: basic theorem, Fleury's algorithm.

- Hamiltonian graphs: Hamilton's game, Dirac's theorem, Ore's theorem.

- Planar graphs: Euler's formula, Kuratowski's theorem, regular polyhedra.

- Colouring planar graphs: history of the four colour theorem, proof of the five colour theorem.

- Colouring other graphs: the chromatic number, the chromatic polynomial and algorithms for their calculation.

- Networks: the Maximal Flow problem, Minimal cuts and the Ford-Fulkerson algorithm, the shortest path algorithm. Critical Path analysis and the longest path algorithm.

- Ramsey theory: Ramsey's theorem, Ramsey numbers.

- Algebraic graph theory: the eigenvalue method.

- Graphical enumeration.

Students will be given the opportunity to use software packages to explore some of the above areas. Those studying the Symbolic Computation course (MT4111) can implement some of the above algorithms in MAPLE.


Introduction to Graph Theory: R J Wilson, Longman; 4th ed. 1996.

Graphs, an Introductory Approach: R J Wilson & J J Watkins, Wiley; 1990.


2 Hour Examination = 100%


MT3501 or MT3503 or MT3504


Academic year 2012/13 in semester 2 at 10


Dr C Bleak

Click here for access to past examination papers for this module.

Click here to see the University Course Catalogue entry.

Revised: PMH (April 2012)

Found a problem with the site? Click here and let us know.