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).

Exam

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

For every n≥3, construct an n-vertex graph with minimum degree n/2-1 or n/2-1/2 (depending on the parity of n) that does not contain a Hamilton cycle.
Show that every orientation of a complete graph has a Hamilton path, i.e., a directed path containing all vertices.
Prove that every graph with minimum degree two contains a cycle.
Show that an n-vertex forest with k connected components has n-k edges.
Show that vertices of any tree can be colored with red and blue in such a way that the end vertices of each edge have different colors.
Show that every connected graph with n vertices and m edges has at least m-n+1 distinct (not necessarily disjoin) cycles.
Show that every plane graph such that each vertex is incident with the outer face has a vertex of degree at most two.
Show that for every n there exists N such that every N-vertex tournament contains the transitive n-vertex tournament as a subgraph.
Determine the clique number and the chromatic number of the complement of an odd cycle.
Show that the chromatic number of a graph G with at least one edge is two if and only if G does not contain an odd cycle a subgraph.
Show that for every family of real intervals such that any two of them have a non-empty intersection, there exists a point contained in all the intervals.
Show that every intersection graph of subtrees of a tree contains a vertex whose neighbors induce a complete subgraph.
Show that every intersection graph of subtrees of a tree is chordal.
Show that a subset of vertices of a graph is independent if and only if its complement is vertex cover.
Show that for every graph the sum of the maximum size of an independent set and the minimum size of a vertex cover is equal to its number of vertices.
Show that the chromatic index of a bipartite graph with maximum degree D is equal to D.
For every k, construct a connected triangle-free graph such that the maximum size of a matching and the minimum size of a vertex cover differ by at least k.
Show that a plane graph is k-edge-connected if and only if its dual does not have a cycle of lenght at most k-1.