This page contains links to miscellaneous addition resources, including pdfs of various sections of the notes, and copies of older notes.
The primary and update to date notes are the html version this allows links and interactive elements. The notes are produced in PreTeXt, a markup language which theoretically allows production of both good html pages and pdfs; I’m focusing on the html element and hopefully the pdfs will be okay.
Other Graph Theory textbooks and notes
- Bondy and Murty’s Graph Theory with Applications includes most of what we do at about the same level, and not too much more
- The same is true of Robin J. Wilson’s Introduction to Graph Theory
- An archive of last year’s website the notes there are close to what we’ll be doing, but not identical
All the source files of the note are hosted on GitHub here (as is this webpage). A description of what exactly GitHub does is here, but it’s an extremely widely used platform for anyone dealing with computers and software and even beyond. If you find any typos or mistakes in the notes, you can fix them yourselves and then issue a pull request, which I can review and then easily apply your fix; you can also file issues if you catch a bug or have an idea for improvement in general.
- 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”
- 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).
- 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 4, use the nearest neighbour heuristic instead of nearest-insertion.