The lectures will take place at 4pm every Thursday (starting on October 8) using the zoom platform; the link will be provided by e-mail. The lectures will be recorded and made available in the information system. The participants are welcome to switch off video and discuss possible privacy concerns with the lecturer.

The tutorials will run biweekly from the week starting on October 12, i.e., there are no tutorials in the first week of the term. Initially, all tutorials will be organized on-line via zoom only; it is almost certain that the tutorials will be held on-line during the whole term. There will be no recording of tutorials to encourage active participation.

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 format of the exam will be either a written in person exam or a remote on-line exam.
The format will be determined based on the COVID situation in January and February 2021.~~
The exam will a remote on-line exam lasting approximately 15-20 minutes.
To register for an exam, it is necessary to satisfy the requirement for the course credit.
The days when it is possible to take an exam are all Tuesdays and Thursdays during the exam period
with the exception of February 2 and 4,
which amount to a total of 10 exam slots.
It is possible to register and unregister until 33 hours (midnight two days earlier) before each of the exam slots;
additional technical instructions to those registered how to take the exam will be sent to those who have registered
when the registration for the particular exam slot has closed.

The credit (zápočet) requirement is the same as the condition for registering for an exam.
To register for an exam, it is necessary to obtain 16 points from homework assignments.
There will be four problem sheets, each containing 3 problems, each problem worth 3 points, i.e., 9 points per sheet.
The deadlines for turning in solutions will be ~~November 6~~ November 7, December 4, January 15 and February 12.
Each of the problem sheets will be published at least about 2 weeks before the deadline.
The solutions can be submitted using the university information system;
resubmissions of solutions that have been graded are not allowed.
The problems in the last problem sheet will be harder than those in the first three and
those submitted by January 29 in the "early deadline" submission vault in the information system
will be marked in a way that it is possible to register for any exam slot taking place in February.

- Problem set #1 - deadline November 6
- Problem set #2 - deadline December 4
- Problem set #3 - deadline January 15 (early deadline January 8)
- Problem set #4 - deadline February 12 (early deadline January 29)

A brief summary of the topics covered during the lectures will be posted here. The recording of the lectures is available in the university information system..

Date |
Lecture content |
---|---|

8/10/2020 | basic definitions: graph, specific graphs (complete graphs, cycles, paths), subgraph, graph minor, graph isomorphism, vertex degree, connectivity, connectivity components, path, walk, tree, forest |

15/10/2020 | Eulerian tour and Euler's Theorem on its existence, directed graphs, strong connectivity, planar vs. plane graph, face of a plane graph, boundary/facial walk, Kuratowski's Theorem (without proof) |

22/10/2020 | number of edges of a tree, Euler's formula, plane triangulations, number of edges of a planar graph, non-planarity of graphs with K_{5} minor, planar drawings with a chosen outerface |

29/10/2020 | vertex and edge colorings, Five Color Theorem, dual of a plane graph, equivalence of the Four Color Theorem and 3-edge-colorability of planar cubic bridgeless multigraphs |

5/11/2020 | Brooks' Theorem and its proof, Vizing's Theorem (without proof), list colorings, an example of a bipartite non-2-list-colorable graph and an example of a planar non-4-list-colorable graph |

12/11/2020 | Thomassen's Theorem on 5-list-colorability of planar graphs, equivalent definitions of a tree, a reminder of basic properties of a tree, existence of a spanning tree |

19/11/2020 | Minimum Spanning Tree (MST) problem - greedy algorithm and its implementation, edge-connectivity, 2-edge-connected graphs, Nash-Williams Theorem (without proof) |

26/11/2020 | vertex-connectivity, Max-flow Min-cut Theorem for unit edge capacity, Menger's Theorem in both vertex-connectivity and edge-connectivity versions |

3/12/2020 | structure of 2-connected graphs, matching, perfect matching, vertex cover, Kőnig's Theorem, Hall's Theorem |

10/12/2020 | structure of 3-connected graphs, proof of Kuratowski's Theorem, flow networks and Max-flow Min-cut Theorem (sketch of proof), networks with integral capacities |

17/12/2020 | classes P and NP, NP-complete problems, NP-completeness of 3-CNF formula satisfiability, graph 3-colorability and vertex cover, Π_{2}-completeness of 3-list coloring (without proof) |

Sample solutions can be found in the university information system. (authentification required).

- Prove that every graph with minimum degree two contains a cycle.
- Prove that if two vertices are joined by a walk in a graph, they are also joined by a path.
- Prove that a graph G contains K
_{3}as a minor if and only if G is not a forest. - Prove that the following holds for any two graphs G and H: G contains H as a minor if and only if
there are disjoint subsets U
_{v}of vertices of G that are indexed by vertices v of H, each set U_{v}induces a connected subgraph of G, and if vv' is an edge in H, then there is an edge between the sets U_{v}and U_{v'}in G. - Prove that every connected bipartite planar graph that is a not a star is a subgraph of a quadrangulation with the same vertex set.
- Prove that every connected bipartite planar graph with n≥3 vertices has at most 2n-4 edges.
- Prove that K
_{3,3}is not planar. - Prove that every bipartite planar graph has a vertex of degree at most three.
- Construct a triangle-free graph with chromatic number four.
- Show that the chromatic index of the Petersen graph is four.
- Compute the list chromatic number of the graph K
_{2,n}for every n. - Show that the list chromatic number of the graph K
_{10,10}is larger than three. - Show that the list chromatic number of an even cycle is equal to two.
- Show that the list chromatic number of the graph K
_{2,2,2}is three. - Prove that every graph obtained from a tree by adding an edge contains exactly one cycle..
- Show that a spanning tree T of an edge-weighted graph G is minimal if and only if for every edge e the weight of every edge contained in the unique cycle of the graph T+e is at most the weight of e.
- Show that a bipartite graph G with parts A and B, |A|=|B|, has a perfect matching if and only if every subset W of A has at least |W| neighbors in B.
- For every k, construct a connected triangle-free graph G such that the size of its minimum vertex cover is at least k larger than the size of its maximum matching.
- Show that the list chromatic number of the complete n-partite graph K
_{2,...,2}is equal to n.*Hint: Use Hall's Theorem.* - Show that the problem SAT can be polynomially reduced to the problem 3-SAT.
- Show that the problem INDSET is NP-complete.
*Hint: Use that the problem VCOVER is NP-complete.*

The problem INDSET is to decide whether an input graph has an independent set of a given size (which is part of input), and the problem VCOVER is to decide whether an input graph has a vertex cover of a given size (which is part of input). - Design an algorithm that runs in time O(2
^{k}n^{2}) and decides whether an n-vertex graph has a vertex cover of size at most k.