MAS341 Graph Theory

Semester 2, 2019/20 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 (or vertices), some pairs of which are joined by lines (or edges). Their basic nature means that they can be used to illustrate a wide range of situations - for example, computer networks and road systems. Graph theory is a huge area, and this module surveys a few fun topics. After an introduction covering trees, and Eulerian and Hamiltonian graphs, the module has units on graph algorithms, drawing graphs on the plane or other surfaces, and on graph colouring.

Prerequisites: MAS211 (Advanced Calculus and Linear Algebra)
No other modules have this module as a prerequisite.


Outline syllabus

  • Introduction: handshaking, some applications, isomorphisms, trees, Hamiltonian and Eulerian graphs
  • Algorithms: shortest paths, cheapest spanning trees, and bounding the Travelling Salesman problem
  • Graph on surfaces: Planarity algorithm, Kuratowski's and Euler's Theorems
  • Colouring graphs: chromatic number, index, and polynomial

Office hours

Monday 11-12, Thursday 2-3, or by appointment



Aims

  • Gain a basic familiarity with graphs, their properties, and applications
  • Improve familiarity with proof in a concrete setting
  • Learn basic graph theoretic algorithms and their limitations

Learning outcomes

  • Determine whether example graphs satisfy basic definitions
  • Prove selected graph theory theorems and lemmas
  • Run standard graph-theoretic algorithms by hand on small examples
  • Adapt standard proof techniques (e.g. Euler's formula + handshaking; deletion-contraction + induction, ...) to novel situations
  • Draw an example graph on a Mobius band or Torus
  • Calculate the chromatic number, index, and polynomial of a graph

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

Basic definitions. The Handshaking lemma. First application: Instant Insanity. Isomorphisms of graphs.
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; applications to chemistry. Proving Cayley's count of label trees using the Prufer code.
3. Eulerian and Hamiltonian 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. Proving or disproving a graph is Hamiltonian "by hand". Ore's theorem.
4. Algorithms
Weighted graphs. Dijkstra's algorithm for shortest path and its limitations. Longest paths and applications to scheduling. Prim and Kruskal's algorithm for finding minimal spanning trees. Bounding the Travelling Salesman problem.
5. Graphs on surfaces
K3,3 and K5 are not planar; the Planarity Algorithm for Hamiltonian graphs; Kuratowski's Theorem; Euler's Formula and applications; drawing graphs on the torus and Mobius band.
6. Graph colouring
The chromatic number and index. Calculating in simple examples, applications. The chromatic polynomial: proving it's a polynomial via deletion-contraction.

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.

Timetable

Mon 15:00 - 15:50 lecture   Hicks Lecture Theatre C
Fri 16:00 - 16:50 lecture   Hicks Lecture Theatre 7