## MAS341 Graph Theory

Semester 2, 2018/19 | 10 Credits | ||||

Lecturer: | Dr Paul Johnson | Home page | Reading List | ||

Aims | Outcomes | Teaching Methods | Assessment | Full Syllabus |

A "graph" is a simple mathematical structure consisting of a collection of points, some pairs of which are joined by lines. Their basic nature means that they can be used to illustrate a wide range of situations. The aim of this course is to investigate the mathematics of these structures and to use them in a wide range of applications. Topics covered include trees, Eulerian and Hamiltonian graphs, planar graphs, embedding of graphs in surfaces, and graph colouring.

**Prerequisites:** MAS211 (Advanced Calculus and Linear Algebra)

No other modules have this module as a prerequisite.

## Outline syllabus

- Definition and examples
- Trees
- Eulerian graphs
- Hamiltonian graphs
- The Travelling Salesman Problem
- The Shortest and Longest Path Algorithms
- Planar graphs
- Embedding graphs in surfaces
- Vertex colouring
- Edge colouring
- Face colouring

## Aims

- To expound the theory of graphs with brief consideration of some algorithms

## Learning outcomes

- Draw standard graphs
- Know when a connected graph is a tree and how trees arise in applications
- Prove Euler's result on Eulerian graphs and apply Fleury's algorithm
- Prove Ore's result on Hamiltonian graphs and be able to find good upper and lower bounds to a Travelling Salesman problem
- Apply the Shortest and Longest Paths Algorithms and handle an Activity Network
- Show that a graph is not planar by finding a subgraph which is
a subdivision of K
_{3,3}or K_{5} - Apply the Planarity Algorithm
- State and prove Euler's Formula and use it
- Embed given graphs in a Möbius band or on a torus
- Calculate the chromatic number and chromatic index of a given graph
- Prove the Five Colour Theorem
- Calculate the chromatic polynomial of a graph using the algorithm

## Teaching methods

Lectures, problem solving

20 lectures, no tutorials

## Assessment

One formal 2.5 hour written examination. All questions compulsory.

## Full syllabus

**1. Definitions and examples**

_{n}and K

_{r,s}, the complement, paths and cycles; the handshaking lemma.

**2. Trees**

A connected graph with v vertices has at least v−1 edges and is a tree if and only if it has exactly v−1 edges; spanning trees; fundamental systems of circuits; Kruskal's Algorithm; aliphatic compounds in chemistry; bracings; electrical networks.

**3. Eulerian graphs**

The edges of a graph can be partitioned into disjoint circuits if and only if every vertex has even degree; a connected graph is Eulerian/semi-Eulerian if and only if every vertex has even degree/it has exactly two vertices of odd degree; Fleury's Algorithm; the Chinese Postman Problem.

**4. Hamiltonian graphs**

Ore's Theorem and Dirac's Theorem; the Travelling Salesman Problem.

**5. The Shortest/Longest Path Algorithm**

Activity Networks.

**6. Planar graphs**

K

_{3,3}and K

_{5}are not planar; Kuratowski's Theorem (statement only); the Planarity Algorithm for Hamiltonian graphs; Euler's Formula for a plane, connected graph.

**7. Embedding graphs in surfaces (survey)**

The torus, Möbius strip and Klein bottle; genus; generalization of Euler's formula.

**8. Vertex- and face- colouring**

The chromatic number; a simple graph is bipartite if and only if every circuit is of even length; a simple graph with maximum vertex-degree ∆ is (∆+ 1)-vertex-colourable; Brooks' Theorem (statement); proof of the five-colour Theorem; Heawood's Formula and the Ringel-Youngs Theorem (statement); the chromatic polynomial.

**9. Edge-colouring**

The chromatic index; χ′(K

_{n}); Vizing's Theorem; χ′(G)=∆(G) for every bipartite G; relationship between edge- and face- colouring for 3-regular planar graphs.

## Reading list

Type | Author(s) | Title | Library | Blackwells | Amazon |
---|---|---|---|---|---|

B |
Bryant | Aspects of combinatorics | 519.21 (B) | Blackwells | Amazon |

B |
Wilson | Introduction to graph theory | 513.83 (W) | Blackwells | Amazon |

C |
Wilson | Four colours suffice | 513.83 (W) | Blackwells | Amazon |

(

**A**= essential,

**B**= recommended,

**C**= background.)

Most books on reading lists should also be available from the Blackwells shop at Jessop West.