# School of Mathematics and Statistics

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

2013/2014 Sem. 1

## Aims

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.

## Objectives

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.

## Textbooks

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

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

## Assessment

2 Hour Examination = 100%

## Prerequisites

MT3501 or MT3503 or MT3504

## Availability

Academic year 2012/13 in semester 2 at 10

Dr C Bleak