SubjectsSubjects(version: 901)
Course, academic year 2022/2023
Combinatorics and Graph Theory 2 - NDMI012
Title: Kombinatorika a grafy 2
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2021
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: prof. Mgr. Zdeněk Dvořák, Ph.D.
doc. RNDr. Vít Jelínek, Ph.D.
Class: Informatika Bc.
Classification: Informatics > Discrete Mathematics
Incompatibility : NDMX012
Interchangeability : NDMX012
Is incompatible with: NDMA002, NDMI032, NDMX012
Is interchangeable with: NDMI032, NDMX012, NDMA002
Annotation -
Last update: T_KAM (20.04.2008)
The lecture extends NDMI011. An overview lecture on classical results in combinatorics and graph theory.
Course completion requirements -
Last update: Irena Penev, Dr. (14.02.2022)

Tutorial credit is a prerequisite for taking the exam. The exam will be written. More details can be found on the course web page:

Literature -
Last update: doc. RNDr. Vít Jelínek, Ph.D. (23.06.2016)

R. Diestel: Graph theory, 3rd edition, Springer, 2005.

H. Wilf: Generatingfunctionology (

Requirements to the exam -
Last update: Irena Penev, Dr. (14.02.2022)

The exam will be written.

Syllabus -
Last update: prof. Mgr. Zdeněk Dvořák, Ph.D. (27.09.2020)

Matchings in general graphs.

Hamiltonian cycles, Ore condition, Chvátal closure.

Surfaces of higher genus, generalized Euler's formula, Heawood's formula.

Lemma on the contractible edge, Tutte's theorem on 3-connected graphs, Kuratowski's theorem.

Graph coloring, Brooks' theorem, Vizing's theorem.

Tutte polynomial: equivalent definitions, important points, cycle space, and cut space of a graph.

Ordinary and Exponential Generating Functions.

Burnside's lemma, Polya's enumeration, examples of applications.

Sunflower theorem, Erdös-Ko-Rado Theorem, Turan's Theorem

Perfect graphs, Dilworth's theorem.

Chordal graphs.

Charles University | Information system of Charles University |