This is the course website for MAS341: Graph Theory at the University of Sheffield, Spring 2017.
Lecture notes as a pdf
Problem sets and Solutions
- Problem Set 1 and Solutions
- Problem Set 2 and Solutions
Solutions to the practice problems
Old exams and solutions
Short notes on what proofs may be examined.- 2016 Exam and Solutions
We didn't discuss Euler characteristic of arbitrary surfaces, so 4ii is not an appropriate question this year; perhaps replace it with "State Euler's theorm for graphs drawn on the sphere. Define a spanning tree, and the dual graph of a planar graph. Sketch the proof of Euler's theorem we gave in lecture that used these ideas" - 2015 Exam and Solutions
We didn't cover 1.i (though it's just an application of whether a certain graph is connected or not) For 2.i.a, you can use the nearest neighbour instead of nearest-insertion. We didn't quite cover 3.i, either (though it's not so far from what we've done). - 2014 Exam and Solutions
You can skip ii.a. We didn't quite use the language of 2.ii, but it's essentially asking you to prove Euler's theorem characterising Eulerian graph. For question 3, k-regular means every vertex has degree k, and G^c is the complement -- it has the same vertices in G, but two vertices v and w are adjacent in G^c if and only if they are not adjacent in G. For question 4, use the nearest neighbour heuristic instead of nearest-insertion.
