MA010 Graph Theory

The lectures take place at 4pm every Thursday (starting on September 15) in the lecture room A217.

The tutorials run biweekly. The tutorials start on September 19 and 26, respectively. There are four tutorial groups and each group will have 6 tutorials during the term, i.e., the last tutorials will take place on November 28 and December 5, respectively.

More detailed information on the course can be found at the course webpage in the university information system..

Materials for the course can also be found in the university information system. (authentification required).


The exam is intended to be a written in person exam if the energy/pandemic situation in January and February permits. To register for an exam, it is necessary to obtain at least 16 points from homework assignments (see below). The exam can be taken on January 13, January 30, February 3 and February 10, on each of the days at 9am. It is possible to register and unregister until the midnight on the day before the exam. Note that the capacity of the slots on January 30 and February 3 is limited as no large lecture room is available in the faculty building.

Registration for an exam

To register for an exam, it is necessary to obtain 16 points from homework assignments. There will be three problem sheets, each containing 4 problems, each problem worth 3 points, i.e., 12 points per sheet. The deadlines for turning in solutions will be October 14, November 11 and December 9. The solutions can be submitted using the university information system; resubmissions of solutions that have been graded are not allowed.

Homework assignments

Lecture content

A brief summary of the topics covered during the lectures will be posted here.

Date Lecture content
15/9/2021 basic definitions: graph, specific graphs (complete graphs, complete bipartite graphs, cycles, paths), subgraph, induced/spanning subgraph, graph isomorphism, vertex degree; Hand-shaking lemma, Hamilton cycle, Dirac's Theorem, Ore's Theorem, directed graphs, vertex in-degree and out-degree
22/9/2021 definition and basic properties of: path, trail, walk, connected graph, connectivity components, tree, forest, leaf; Eulerian tour and Euler's Theorem
29/9/2021 equivalent definitions of a tree, plane drawing, plane graph vs. planar graph, face, facial walk, dual graph
6/10/2022 plane graphs are spanning subgraphs of plane triangulations, Euler's Formula, maximum number of edges of a planar graph and the existence of a vertex of degree at most five, Kuratowski's Theorem (statement only)
13/10/2022 Ramsey's Theorem (with any number of colors), vertex coloring, chromatic number, ω≤χ≤Δ+1, triangle-free graphs with arbitrary large chromatic number, Four Color Theorem (statement only), Five Color Theorem
20/10/2022 Brooks' Theorem, edge coloring, chromatic index, Vizing's Theorem
27/10/2022 definitions of perfect graphs, chordal graphs and interval graphs, Perfect Graph Theorem (statement only), chordal graphs are perfect, Helly's property of subtrees of a tree, chordal graphs are intersection graphs of subtrees of a tree
3/11/2022 Hall's Theorem for set systems, definitions of a matching and a perfect matching, Hall's Theorem for bipartite graphs, k-regular bipartite graphs: existence of a perfect matching and k-edge-colorability, definition of vertex cover, Kőnig's Theorem (to be proven at the next lecture)
10/11/2022 proof of Kőnig's Theorem, definitions of an independent set and the independence number, Gallai-Milgram's Theorem, definitions of a chain and an antichains of partially ordered set, Dilworth's Theorem
24/11/2022 vertex-connectivity and edge-connectivity of graphs, existence of edge-disjoint paths in directed graphs, Menger's Theorem both for vertex-connectivity and edge-connectivity
8/12/2022 definition of list coloring and list chromatic number, existence of bipartite graphs with arbitrary large list chromatic number, list edge-coloring, list coloring of planar graphs (Thomassen's and Voigt's Theorems)

The content of the lecture on December 8 is non-examinable.

Exercise problems