MA010 Graph Theory

The lectures take place at 2pm every Thursday (starting on October 5) in the lecture room A217. The first lecture on October 5 (in the third week of the term) takes place only after each group has had a tutorial and so the first tutorials will be focused on refreshing basic graph theory terminology, which has likely already been seen in different courses taken earlier.

The tutorials run biweekly. The tutorials start on September 25 and October 2, 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 December 4 and December 11, 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).

Exam

The exam will be a written in person exam lasting 90 minutes. 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 Friday January 5, Friday January 26, Wednesday February 7 and Thursday February 15, on each of the days starting at 8am. It is possible to register and unregister until 32 hours before the start of the exam. Note that the number of the slots on February 15 is very limited since no larger lecture room is available on that day.

Registration for an exam

To register for an exam, it is necessary to obtain 16 points from homework assignments. There will be two problem sheets, each containing 4 problems, each problem worth 4 points, i.e., 16 points per sheet. The deadlines for turning in solutions will be November 14 and December 12. 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
5/10/2023	equivalence of the existence of a walk and a path, definition of a tree and three additional equivalent definitions of a tree, Pósa's Theorem and Ore's Theorem (statements only)
12/10/2023	proof of Ore's Theorem, Euler's Theorem and its proof, planar drawing, plane graph vs. planar graph, face, plane graphs are spanning subgraphs of plane triangulations
19/10/2023	Kuratowski's Theorem (statement only), Euler's Formula, number of edges of a planar graph and the existence of a vertex of degree at most five, vertex coloring, chromatic number, Four Color Theorem (statement only), Five Color Theorem, ω≤χ≤Δ+1
26/10/2023	Ramsey's Theorem, construction of triangle-free graphs with abritrarily large chromatic number, Brooks' Theorem
2/11/2023	perfect graphs, Weak Perfect Graph Theorem and Strong Perfect Graph Theorem (statements only), chordal graphs are perfect, interval graphs and intersection graphs of subtrees of a tree
9/11/2023	Helly's Theorem (statement only), Helly Property of subtrees of a tree, chordal graphs are exactly intersection graphs of subtrees of a tree, Hall's Theorem for set systems
23/11/2023	matching, perfect matching, Hall's Theorem for graphs, edge-coloring, chromatic index, the line graphs of bipartite graphs are perfect, Vizing's Theorem
30/11/2023	vertex cover, König's Theorem, vertex-connectivity and edge-connectivity, Menger's Theorems (statements only), existence of disjoint directed paths, proof of Menger's Theorem for edge-connectivity
14/12/2023	proof of Menger's Theorem for vertex-connectivity, posets, chains and antichains, Dilworth's Theorem, Gallai-Milgram Theorem

Exercise problems

Show that a graph is a tree if and only if it has no cycle but adding any edge creates a cycle.
Show that every graph with minimum degree at least two has a cycle.
Show that every graph with minimum degree at least two has an induced cycle, i.e., an induced subgraph that is a cycle.
Show that every outer-planar graph with n>=2 vertices, i.e., a graph that can be drawn in the plane in a way that all vertices are incident with the outer face, has at most 2n-4 edges.
Compute the clique number and the chromatic number of the complement of the cycle of length n>=4.
Show that a graph G is 2-colorable if and only if G does not contain an odd cycle.
Show from the first principles, i.e., without using statements from the lectures, that if P₁,...,P_k are subpaths of a path such that any two of them have a vertex in common, then there exists a vertex contained in all paths P₁,...,P_k.
Show that every chordal graph has a vertex such that any two of its neighbors are joined by an edge, i.e., its neighbors induce a complete graph.
Show that every bipartite graph with maximum degree D is a subgraph of a D-regular bipartite graph, i.e., a bipartite graph whose every vertex has degree D.
Show that a subset A of vertices of a graph is independent if and only if the complement of A is a vertex cover.
Show for every graph that the sum of the maximum independent set and the minimum vertex cover is equal to its number of vertices.
Show that every (simple) planar graph has an orientation such that the in-degree of every vertex is at most three.
For every k construct a connected triangle-free graph G such that the difference between the minimum size of a vertex cover of G and the maximum size of a matching is at least k.
Show that every 3-edge-connected 3-regular graph is 3-vertex-connected. (A graph is 3-regular if every vertex has degree three.)
Show that the chromatic number of every chordal k-vertex-connected graph is at least k+1.