MATH 361 (2024) - Home Page

Welcome to the website for MATH 361: Graph Theory. All course-related material will be available here.

---

Announcements

• Assignment 4 is available below. Due 14 May.
• The mid-course test has been marked. Marks are available on nuku, and see here for info on how you can view your script over the reconsideration period (30 April to 13 May). Some example solutions for the test are below.

---

Course information

• Course information.
• Lectures are at 3:10-4pm on Mondays, Tuesdays, and Wednesdays, in Hugh Mackenzie Lecture Theatre 103.
• Tutorials are at 3:10-4pm on Fridays in LT103, Hugh Mackenzie, starting from the first week. Sam Bastida will be your tutor for this course.
• The course coordinator and lecturer is Nick Brettell. My office hours are 4:10-5:00pm on Tuesday (after the lecture) in my office (Cotton 427).

---

Course notes and lecture notes

Lecture recordings will be available on panopto (you can access these via nuku).

Course notes	Lecture notes
1. The Basics, and the unredacted version	Lecture 1
	Lecture 2
2. Trees, and the unredacted version	Lecture 3
	Lecture 4
	Lecture 5
3. Connectivity, and the unredacted version	Lecture 6
	Lecture 7
	Lecture 8
	Lecture 9
	Lecture 10
	Lecture 11
	Lecture 12
4. Planar graphs I	Lecture 13
	Lecture 14
	Lecture 15
	Lecture 16
	Lecture 17
5. Planar graphs II	Lecture 18
	Lecture 19
	Lecture 20
	Lecture 21
	Lecture 22
	Lecture 23
6. Colouring	Lecture 24
	Lecture 25
	Lecture 26

---

Assessment

There will be 5 assignments (worth 6% each), a mid-course test (worth 20%), and a final (externally managed) test (worth 50%).

Assignments and Tutorials

Assignments and related tutorial questions will appear together (below). Your assignments should be submitted (online) using nuku. The assignments are due 3pm on Tuesdays, roughly every other week (precise dates are below).

	Due date	Solutions
Assignment 1	11 March	Solutions
Assignment 2	26 March	Solutions
Assignment 3	30 April	Solutions
Assignment 4	14 May
Assignment 5	28 May

Test

The test was held on Monday 15 April, at the normal lecture time (3:10 - 4:00pm). Some solutions can be found here.

For practice, you can look at past tests from 2023, 2022, or 2020. Last year's test is a reasonable model of what to expect, though there have been some changes to content compared to last year.

Related material

Although there is no set text for the course, the following are good references:

• "Graph Theory", by R. Diestel (5th edition 2017)
• "Graph Theory", by J.A. Bondy and U.S.R. Murty (2008)

Tangential material

Occasionally I like to mention tangential material in lectures, but there is limited time to go into detail. If you'd like to read further, see here for inspiration.

• In lecture 1, we discussed the Seven Bridges of Königsberg.
• In lecture 4, I mentioned minimum weight spanning trees
• In lecture 7, I mentioned Menger's theorem, but we will return to this again very soon...
• In lecture 14, we touched on the interesting mathematical field of topology.
• In lecture 17, I had several tangents: I mentioned Bill Tutte, and the Bletchley park codebreaking efforts (see also the links in the 4th set of course notes), and I mentioned Tutte's interest in matroids, and how they can be studied further in MATH432. Finally, we also mentioned stereographic projections.
• In lecture 18, we saw Euler's formula -- see here and here for more on the connection with polyhedra.
• In lecture 19, we scratched the surface of Robertson and Seymour's Graph Minors Theorem
• In lecture 23, we talked about linklessly embeddable graphs, the Petersen family, and YΔY-reducible graphs.
• In lecture 25, we mentioned the mathematical pseudonym Blanche Descartes.