MAS341 Graph Theory

Semester 2, 2017/18 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 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.

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.