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 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, December 4, January 15 and February 12; the problems in the last problem sheet will be significantly harder than those in the first three. Each of the problem sheets will be published about 2 weeks before the deadline. The solutions can be submitted using the university information system.

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 |

The problem sheets will be posted here.

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