max planck institut
mpii logoMinerva of the Max Planck Society

Graph Theory (Summer 2013)

Basic Information

Lectures: Tuesday 14-16 (R.024 E1.4) / Thursday 14-16 (R.024 E1.4)
Lecturers: Artur Jez and Jens M. Schmidt 
Tutorials: Wednesday 16-18 (R.023) and Friday 14-16 (R.022)
Tutors: Andreas Schmid, Harry Zisopoulos


This is a first course in graph theory dedicated to both, computer science and mathematics students. Topics include basic notions like graphs, subgraphs, trees, cycles and further concepts like connectivity, packing, colorings, matchings, planarity, perfect graphs, random graphs, minors etc..

Prerequisites: Basics in discrete mathematics, probability theory and calculus.
Literature:Most of the lecture, but not all, will follow Reinhard Diestel's book on graph theory. There is a free PDF-version on this page.
Credit: SWS: 4+2, Credit Points: 9
Exam: There will be an oral or written exam at the end of the semester, depending on the number of students. Your grade will only be dependent on the exam.


Date Topic Lecturer Exercises
Apr 16 Basic techniques, graphs, degrees, cycles, Handshake lemma, k-(edge-)connectivity Jens Exercise 1
Apr 18 Trees, bipartite graphs, Eulerian graphs, subdivisions and minors Jens
Apr 23 Matchings, König's theorem, Hall's theorem, stable matchings Artur Exercise 2
Apr 25 Tutte's perfect matching theorem, connection to determinants Artur
Apr 30 Nash-Williams' tree-packing theorem Jens Exercise 3
May 2 2-connectivity, blocks, BC-tree, Menger's theorem and variants Jens
May 7 Linkages Jens Exercise 4
May 9 No lecture (Ascension Day)
May 14 Flows, Ford-Fulkerson theorem (Room Change: R.023)Artur Exercise 5
May 16 Circulations, nowhere-zero-flows and Tutte's conjecturesArtur
May 21 Graph coloring, chromatic number, greedy algorithm, Brook's theorem
Artur Exercise 6
May 23 Chromatic index, Coloring bipartite graphs, Vizing's theoremArtur
May 28 Chordal graphs, perfect graphs, perfect graph theorem (weak version)Artur Exercise 7
May 30 No lecture (Corpus Christi)
June 4 List colorings, edge-list coloring conjecture, Galvin's theoremJens Exercise 8
June 6 Planar graphs, embeddings+duality, 5-color theorem, discharging method and 4-color theoremJens
June 11 Euler's formula, high genus surfaces, graph genus, Kuratowski's criterion, crossing numberArtur Exercise 9
June 13 Extremal graphs: Hadwiger's conjecture, Heawood bound for high genus graphsArtur
June 18 cancelled

tutorials take place!
June 20 cancelled
June 25 WQO and consequences, graph minor theorem, hereditary propertyArtur Exercise 10
June 27 Kruskal's tree theorem, tree decompositionsArtur
July 2 Conditions for small treewidth, partial k-trees, brambles, tree-width dualityJens Exercise 11
July 4 Cops and robber games, infinite graphs, König's lemma
July 9 Hamiltonian cycles, sufficient conditionsJens Exercise 12
July 11 Necessary conditions, Grinberg's theorem, Chvatal's theorem, Barnette's conjectureJens Barnette's Conjecture Slides
July 16 Platonic Solids, edge- and cycle space, cycle bases, Tutte's theorem on non-separating induced cycles basesJens Exercise 13
July 18 Maximum adjacency orderings, sparse k-edge-connected subgraphs, pendant pairs, Stör-Wagner Jens
July 23 Ramsey theorem and generalizations, random graphs, probabilistic methodArtur
August 2+513:00-18:00: ExamsArtur+Jens
October 7-9Re-exams (by appointment)Artur+Jens

More Courses of the Algorithms and Complexity Group
Search MPII (type ? for help)