MA010 Graph Theory

The lectures take place at 10am every Tuesday (starting on September 24 and concluding on November 26) in the lecture room A217.

There are two tutorial groups and each group will have 6 tutorials during the term. The tutorials run biweekly; the first tutorial for the the first tutorial group takes place on Wednesday October 2 (8am in A217) and the one for the second takes place on Thursday October 3 (2pm in B411). The last two tutorials will take place on December 4 and 5 instead of December 11 and 12.

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 will be possible to take on Friday December 13, Thursday January 2, and Thursday January 16.

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 October 24 and December 5; the problem sheets will be made available in a way that each tutorial group has one tutorial between the publication of a homework sheet and the associated deadline. The solutions should 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
24/9/2024	basic definitions: graph, specific graphs (complete graphs, complete bipartite graphs, cycles, paths), graph isomorphism, vertex degree, subgraph, induced/spanning subgraph; Hand-shaking lemma, Hamilton cycle, Dirac's Theorem, Ore's Theorem, path/trail/walk, equivalence of the existence of a walk and a path, graph connectivity
1/10/2024	Euler's Theorem and its proof, planar drawing, plane graph vs. planar graph, face, plane graphs are spanning subgraphs of plane triangulations, Kuratowski's Theorem (statement only)
8/10/2024	definition of a tree and four additional equivalent definitions of a tree, Euler's formula for plane graphs
15/10/2024	number of edges of a planar graph and the existence of a vertex of degree at most five, vertex coloring, chromatic number, χ≤Δ+1, Four Color Theorem (statement only), Five Color Theorem, Ramsey Theorem, Erdős–Szekeres Theorem (statement only)
22/10/2024	construction of triangle-free graphs with high chromatic number, Brooks' Theorem
29/10/2024	perfect, chordal and interval graphs, Weak Perfect Graph Theorem and Strong Perfect Graph Theorem (statements only), chordal graphs are perfect, Helly's Theorem and Helly property of subtrees of a tree (statements only), chordal graphs are exactly the intersection graphs of subtrees of a tree, interval graphs are chordal
5/11/2024	proof that subtrees of a tree have the Helly Property, Hall's Theorem on the existence of a system of distinct representatives, matching, perfect matching, Hall's Theorem on the existence of a perfect matching in a bipartite graph, vertex cover, König's Theorem
12/11/2024	edge coloring, chromatic index, equivalent formulation of the Four Color Theorem (without proof), Vizing's Theorem, posets, chains and antichains, Dilworth's Theorem, Gallai-Milgram Theorem
19/11/2024	vertex-connectivity and edge-connectivity, existence of disjoint paths in directed multigraphs, Menger's Theorem for vertex-connectivity, Menger's Theorem for edge-connectivity
26/11/2024	notion of graph minors, minor-closed classes of graphs and testing existence of a minor (without proofs), existence of a contractible edge in a 3-connected graph, proof of Kuratowski's Theorem, embedding graphs in orientable surfaces, generalized Euler's formula (proof hinted), Heawood's Theorem (without proof)

Exercise problems

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.
Decide whether the Petersen graph has a Hamilton cycle.
Show that if an n-vertex graph G has at least (n²-3n+6)/2 edges, then G has a Hamilton cycle.
Show that a connected graph G with maximum degree Δ such that not all vertices of G have degree Δ is Δ-colorable.
Show that a graph G is 2-colorable if and only if G has no odd cycle.
Construct a triangle-free 4-chromatic graph.
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-3 edges.
Show that every chordal graph contains a vertex whose neighborhood is a complete graph.
Show from the first principles that subpaths of a path have the Helly Property.
Show that the complement of any interval graph is perfect.
Show that the chromatic index of the Petersen graph is four.
Show that every bipartite graph with maximum degree D is a subgraph of a bipartite D-regular graph. Use this to show that the chromatic index of every bipartite graph is equal to its maximum degree.
Show that the sum of the maximum independent set and the minimum vertex cover in every graph is equal to its number of vertices.
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 for every n and k, there exists N such that every coloring of edges of K_N,N with k colors contains a monochromatic copy of K_n,n.
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 edges of any planar graph can be oriented in a way that every vertex has at most three incoming edges. Hint: Use Hall's Theorem.
Show that neither K₅ nor K_3,3 is planar.
Show that a graph G contains a subdivision of K₅ or K_3,3 if and only if G contains K₅ or K_3,3 as a minor.
Show that if a graph obtained from a graph G by contracting an edge contains a subdivision of K₅ or K_3,3, then G contains a subdivision of K₅ or K_3,3.
Show that every graph on the torus contains a vertex of degree at most 6.
Show that K₇ can be drawn on the torus.