This module is discontinued in the selected year. The information shown below is for the academic year that the module was last running in, prior to the year selected.

# 2013/14 Taught Postgraduate Module Catalogue

## MATH5033M Advanced Graph Theory

### 20 creditsClass Size: 40

**Module manager:** Dr Joseph Grant**Email:** pmtjgr@leeds.ac.uk

**Taught:** Semester 1 (Sep to Jan) View Timetable

**Year running** 2013/14

### Pre-requisites

MATH2210 | Introduction to Discrete Mathematics |

### This module is mutually exclusive with

MATH3033 | Graph Theory |

**This module is approved as an Elective**

### Module summary

This module provides an introduction to the basic ideas such as connectedness, trees, planar graphs, Eulerian and Hamiltonian graphs, directed graphs and the connection between graph theory and the four colour problem. Graph theory is an important mathematical tool in such different areas as linguistics, chemistry and, especially, operational research. The material on complexity theory and algorithmic graph theory is an important bridge between mathematics and theoretical computer science, and is very rich in applications.### Objectives

To introduce students to some of the main concepts and modeling usefulness of graph theory, and to develop their ability to reason graph theoretically.**Learning outcomes**

On completion of this module, students should be able to:

(a) identify basic examples of isomorphic and non-isomorphic pairs of graphs, and make simple deductions involving vertex degrees, connectedness and bipartite graphs;

(b) apply a selection of criteria related to Eulerian and Hamiltonian graphs;

(c) explain and apply the basic theoems for trees, planar graphs and directed graphs;

(d) understand the Max-flow Min-cut Theorem and its connections to other results in graph theory, and apply the Ford-Fulkerson Algorithm.

(e) show a knowledge of graph colourings of various types, and apply a range of techniques for identifying chromatic numbers for graphs and surfaces;

(f) understand and explain key concepts from computational complexity theory;

(g) explain and apply several graph theoretic algorithms, prove their validity and investigate their speed.

### Syllabus

Topics chosen from:

1. Basic definitions. Connected graphs, vertex degrees, bipartite graphs.

2. Adjacency matrices, strongly regular graphs, Friendship Theorem.

3. Eulerian graphs and applications.

4. Hamiltonian graphs, including Dirac's theorem and techniques for identifying non-Hamiltonian graphs.

5. Trees (Cayley's Theorem), line graphs. Multiple connectivity and block graphs.

6. Planar graphs. Euler's theorem, Kuratowski's theorem (without proof).

7. Digraphs, strong connectedness. Robbins' Theorem. Eulerian digraphs. Hamiltonian and semi-Hamiltonian tournaments and Moon's Theorem.

8. Networks. Max-flow Min-cut Theorem (Ford-Fulkerson Algorithm), Menger's Theorem, Konig's Theorem, and applications.

9. Graph colourings. The five-colour theorem for planar graphs, the four-colour theorem for planar graphs (without proof). Brook's Theorem. Edge colourings, Tait colourings.

10. Chromatic numbers of surfaces, applications of the Euler characteristic, Heawood's inequality and the Map Colour Theorem.

11. Graph problems and intractability, including NP-completeness and Cook's Theorem.

12. A selection of graph-theoretic algorithms and associated structural results, from some of the following: minimum connector problem; planarity testing algorithm; electrical networks and searching trees; chromatic polynomials; Menger's Theorems and connectivity; minimum cost-flow; strongly connected and 2-connected components; graph minors.

### Teaching methods

Delivery type | Number | Length hours | Student hours |

Lecture | 44 | 1.00 | 44.00 |

Private study hours | 156.00 | ||

Total Contact hours | 44.00 | ||

Total hours (100hr per 10 credits) | 200.00 |

### Private study

There will be two weekly office hours for students to get additional help, depending on their needs.### Opportunities for Formative Feedback

Regularcoursework with solution sheets provided later.### Methods of assessment

**Exams**

Exam type | Exam duration | % of formal assessment |

Standard exam (closed essays, MCQs etc) | 3 hr 00 mins | 100.00 |

Total percentage (Assessment Exams) | 100.00 |

Normally resits will be assessed by the same methodology as the first attempt, unless otherwise stated

### Reading list

The reading list is available from the Library websiteLast updated: 17/02/2014

## Browse Other Catalogues

- Undergraduate module catalogue
- Taught Postgraduate module catalogue
- Undergraduate programme catalogue
- Taught Postgraduate programme catalogue

Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD