MATH20902 Course Materials

Lecture Notes

The notes linked below will include everything I cover in lecture, but for additional reading I urge you to have a look at the online versions of Dieter Jungnickel's very useful book, Graphs, Networks and Algorithms. I wrote the course while studying a copy of the 2nd edition, but you might also like to look at the 3rd edition, which appeared in 2008. The links above will only work if you are within the University's network. If you are off campus, you can install software that will allow you to access the book through the University's excellent Virtual Private Network (VPN).

Notes such as the ones below will be available for the whole term: the ones here are provided as an example for students considering the course in 2018-19.

to the top

Opportunities for feedback

The main channel for formal, written feedback in this module is the coursework. It will be a problem set similar to the ones provided below, but devoted to an application that uses the ideas from the course. You'll prepare written solutions and I'll mark them over the Easter Break, providing both written comments and a mark. In addition, the weekly examples classes provide further opportunities for verbal feedback and—for students who bring written solutions to the exercises—on-the-spot marking and written feedback as well.

Problem Sets & Solutions

The problem sets, which appear roughly every week throughout the term, are an important part of the course. I always publish the problems and the solutions at the same time.

Problems Solutions

to the top

Coursework & Exams

Coursework Exams

to the top

Intended Learning Outcomes

Once you've successfully completed this module you should be able to:

  • Define what it means for two graphs to be isomorphic and determine, with rigorous supporting arguments, whether two (small) graphs are isomorphic.
  • Explain what the chromatic number of a graph is, determine it for small graphs and apply the idea to scheduling problems.
  • Say what it means for a graph to be Eulerian and determine whether small graphs or multigraphs are Eulerian.
  • Say what it means for a graph to be Hamiltonian and use the Bondy-Chávtal theorem to prove that a graph is Hamiltonian.
  • Construct the graph Laplacian and apply the Matrix-Tree Theorem to count the number of spanning trees or spanning arborescences contained in a graph.
  • Construct the adjacency matrix of a graph and exploit the connection between powers of the adjacency matrix to count walks. Also, define the operations of tropical arithmetic, construct the weight matrix associated with a weighted graph and use its tropical matrix powers to find the lengths of shortest paths.
  • Given a project defined by a set of tasks, along with their their durations and prerequisites, use critical path analysis to determine how quickly the project can be completed.
  • Say what it means for a graph to be planar; state and apply Kuratowski's theorem and determine whether a graph is planar or not.
▲ Up to the top