## MAS341 Graph Theory

 Semester 2, 2018/19 10 Credits Lecturer: Dr Paul Johnson Home page Timetable 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 K3,3 or K5
• 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

Definitions of simple graphs, isomorphism, connected graphs and components of a graph, Kn and Kr,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
K3,3 and K5 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; χ′(Kn); Vizing's Theorem; χ′(G)=∆(G) for every bipartite G; relationship between edge- and face- colouring for 3-regular planar graphs.