This page is for the modules MATH30002 and MATHM0009 Topics in Discrete Mathematics as taught at the University of Bristol in 2013–14. It is not representative of the material in this module now (if it still exists).

This module is taught in three parts:

  1. Error correcting codes, lectured by Dr Jonathan Bober
  2. Introduction to Graph Theory, lectured by me
  3. Graph colouring, lectured by Dr Karen Gunderson

This page is for part 2 of the module, on Introduction to Graph Theory.

Lecture notes

This part of the course is an introduction to some concepts from graph theory. There are five topics (one per lecture) and a problems class:

  1. Graphs: Lecture notes
  2. Paths, circuits, cycles: Lecture notes Handout: Definitions
  3. Bipartite graphs: Lecture notes
  4. Planar graphs: Lecture notes
  5. Graph theory and linear algebra: Lecture notes Handout: Linear algebra facts
  6. Problems class: Problem sheet (2 pages) Solutions (6 pages) Past exam question: question and solutions

Problem sheet

This part of the course has one problem sheet.

There is a past exam question available with worked answers.

Books

It should be possible to learn the material in this part of the course without using a textbook, but you may find them useful.

The main resources I used in writing lecture notes were:

Bollobas is impressively comprehensive – it covers this part of the course, the Graph colouring part of the course, and a great deal more besides. However, it moves through the basic material extremely quickly, and the exercises vary from the pretty difficult to the almost impossible.

Any introductory book on graph theory is likely to cover the material in this part of the course. Some examples I hear good things about are:

  • JA Bondy and USR Murty. Graph Theory. Graduate Texts in Mathematics, Springer, 2008.
  • JA Bondy and USR Murty. Graph Theory and Applications. North-Holland, 1976. Available for free online
  • R Diestel. Graph Theory. Graduate Texts in Mathematics, Springer, 1997. Available for free online
  • R Grimaldi. Discrete and Combinatorial Mathematics: An applied introduction, fifth edition. Pearson, 2014.
  • RJ Wilson. Introduction to Graph Theory, fifth edition. Prentice Hall, 2010. Earlier edition available for free online

Projects

Fourth-year students taking this module as MATHM0009 also must complete a project on some part of the course, for 20% of their mark.

The written project should demonstrate your independent study, an awareness of a broader literature and a critical evaluation of how the basic ideas may be further developed. The project should be neatly typeset (such as in LaTeX), be between 5–10 pages in length, and will be marked on the 0–100 scale for accuracy, clarity, and depth.

Suggested topics on basic graph theory are:

  • The graph isomorphism problem: It can be difficult to tell if two graphs are isomorphic or not. No polynomial algorithm is known for this - although it’s not so hard as to be NP-complete either. A project could discuss the computational complexity of the graph isomorphism problem, and investigate particular families of graphs, such as trees and planar graphs, where it is easier to solve.
  • The Hamiltonian cycle problem: While deciding if a graph has an Eulerian trail or circuit is very easy, deciding if it it has a Hamiltonian cycle (or path) is very hard - it’s NP-complete. A project could discuss the computational complexity of the Hamiltonian cycle problem, and investigate some algorithms used to detect Hamiltonian paths and cycles. Alternatively, a project could investigate sufficient (but not necessary) conditions for Hamiltonian cycles to exist in graphs and directed graphs, generalizing Dirac’s theorem.
  • Algorithms for embedding planar graphs: A project could investigate algorithms for producing an embedding of a planar graph. This project could contain a significant computational aspect.
  • Crossing numbers: Some nonplanar graphs are “almost planar”, in that they can be drawn with very few edge crossings. The crossing number of a graph is the minimum number of edge crossings required to embed a given graph in the plane. A project could investigate some bounds on the crossing number, perhaps concentrating on ‘Turan’s brick factory problem’ on the crossing number of the complete bipartite graph.
  • Further spectral graph theory: In lectures we saw a few properties of the spectrum of the adjacency matrix. A project could prove further properties of the spectrum, including results relating the spectrum to the chromatic number of the graph. A project could also investigate other matrices, such as the Laplacian, that can be associated with a graph.
  • Stable matching: We’ve seen that a matching in a graph ensures each girl and boy can get married to a member of the opposite sex whom they like. More likely, each girl has an order of preference on the boys she knows, and each boy has an order of preference on the girls he knows. A matching where no pair of couples would wish to each get divorced and swap partners is called a stable matching. A project could investigate the existence of stable matchings in bipartite graphs, algorithms for finding them, and analysing when the matching is optimal for one of the genders.