Graph Theory (1MA170), Fall 2023

Welcome to the course in graph theory at the bachelor's level at Uppsala University. For general information about the course - the exam, the handin, and lecture plan, see this document.

Lecture notes and exercise session notes

1. Exercise session 1: Introduction - what is graph theory?
2. Lecture 2: Eulerianity, simple graphs, and subgraphs
3. Lecture 3: Common graph families, trees, and Cayley's theorem
4. Lecture 4: Spectral graph theory and the matrix-tree theorem
5. Exercise session 5: MSTs, flows, Hamilton cycles and independent sets
6. Lecture 6: Weights, distances, and minimum spanning trees (With solutions from two different groups: Here and here.)
7. Lecture 7: The max-flow min-cut and marriage theorems
8. Lecture 8: Vertex covers, Hamilton cycles, independent sets
9. Exercise session 9: Connectivity, planarity, colourings
10. Lecture 10: Connectivity
11. Lecture 11: Planarity
12. Lecture 12: Vertex colourings (With two sets of solutions: A and B)
13. Exercise session 13: The probabilistic method, edge-colourings, and the Rado graph
14. Lecture 14: The probabilistic method and the Erdős-Rényi random graph
15. Exercise session 15: Extremal graph theory and Szemerédi's regularity lemma
16. Lecture 16: Edge-colourings and Ramsey theory
17. Lecture 17: The Rado graph
18. Lecture 18: Extremal graphs and Szemerédi's regularity lemma (Work in Progress)

Other course material

1. In addition to the lecture notes, the book Graph Theory by Reinhard Diestel is listed as course literature, and it may be a useful reference. It ought be available as a pdf from the university library.
2. The lecture notes from last year's edition of the course are available here. The material covered should be mostly the same, just in a slightly different style. These should be useful if you want to read ahead.
3. A summary of the contents of the course, with indications of what may appear on the exam, is available here.

Old exams

There are some old exams available:

1. [Tentamen 150817 Koponen](https://vagdur.github.io/Grafteori-1MA170/old_exams/Tentamen 150817 Koponen.pdf)
2. [Tentamen 170110 1MA170 Thörnblad](https://vagdur.github.io/Grafteori-1MA170/old_exams/Tentamen 170110 1MA170 Thörnblad.pdf)
3. [Tentamen 190611 1MA170 Strömberg](https://vagdur.github.io/Grafteori-1MA170/old_exams/Tentamen 190611 1MA170 Strömberg.pdf)
4. [Tentamen 220110 1MA170 Burghart](https://vagdur.github.io/Grafteori-1MA170/old_exams/Tentamen 220110 1MA170 Burghart.pdf)
5. [Tentamen 230105 1MA170 Burghart](https://vagdur.github.io/Grafteori-1MA170/old_exams/Tentamen 230105 1MA170 Burghart.pdf)

The exam from the 5th January 2024 is here, with solutions here. A report on the results of the exam is available here.

Where to find a paper for the assignment

If you have some specific topic that came up during a lecture that you want to delve deeper into, I may be able to suggest something for you. Otherwise, you can have a look at what was published at some recent conferences in the area. Some of these conferences are about combinatorics more broadly, so not every paper in them will be suitable. One of them is about network science, so it is a good place to look for more applied papers.

1. PCC23 (Combinatorics)
2. FoCM23 (Combinatorics and graph theory)
3. SAND23 (Temporal graphs, more Computer Science-y than mathsy)
4. NetSci2023 (Network Science)
5. EuroComb23 (Combinatorics)

Past group projects

For the groups that did the ``edit lecture notes and solve exercises'' project, all past submissions are in the pull requests of the repository hosting this page and the lecture notes.

There are also the following past projects summarizing papers:

1. Temporal graphs and the firefighter problem
2. Shortest-path algorithms

---

Lecture notes for 1MA170 Graph Theory by Vilhelm Agdur is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Based on a work at https://github.com/vagdur/Grafteori-1MA170.