SubjectsSubjects(version: 901)
Course, academic year 2017/2018
Combinatorics and Graph Theory II - NDMI012
Title: Kombinatorika a grafy II
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017 to 2017
Semester: winter
E-Credits: 6
Hours per week, examination: winter 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: doc. RNDr. Vít Jelínek, Ph.D.
Mgr. Tereza Klimošová, Ph.D.
Class: Informatika Bc.
Classification: Informatics > Discrete Mathematics
Is incompatible with: NDMI032, NDMA002
Is interchangeable with: NDMI032, 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 - Czech
Last update: doc. RNDr. Vít Jelínek, Ph.D. (27.09.2018)

Podmínky získání zápočtu na cvičeních V. Jelínka: pro nárok na zápočet je potřeba získat alespoň 25 bodů za řešení domácích úkolů a za aktivní účast na cvičeních. Povaha kontroly předmětu vylučuje opravné termíny u zápočtů.

Podmínkou konání zkoušky je zisk zápočtu.

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 has an oral form, with students being given an opportunity for a written preparation before the oral examination itself begins. The topics of the exam correspond to the syllabus of the course, as covered by the lectures and the tutorials. The exam may include combinatorial problems that can be solved by applying or generalizing the results presented at the lectures and tutorials.

Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)
  • Tutte's and Petersen's theorem
  • Hamilton cycles, Ore's theorem, Chvátal closure
  • Surfaces of higher genus, generalized Euler's formula, Heawood's formula
  • Tutte's theorem on 3-connected graphs, Kuratowski's theorem
  • Brooks' theorem, Vizing's theorem
  • Tutte polynomial: equivalent definitions, important points
  • Ordinary and exponential generating functions
  • Burnside's lemma, Póla's enumeration
  • Sunflower theorem, Erdös-Ko-Rado theorem, Turán's theorem
  • Dilworth's theorem, perfect graphs
  • Chordal graphs

Charles University | Information system of Charles University |