SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Combinatorics and Graph Theory II - NDMI012
Title in English: Kombinatorika a grafy II
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2018
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: doc. Mgr. Zdeněk Dvořák, Ph.D.
doc. RNDr. Vít Jelínek, Ph.D.
Class: Informatika Bc.
Classification: Informatics > Discrete Mathematics
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: doc. RNDr. Vít Jelínek, Ph.D. (27.09.2018)

To obtain the credit of the tutorial given by Andreas Feldmann: you need to

1. obtain 60% of the total points of the exercise sheets (each sheet is worth 10 points), and

2. obtain 60% of the total points of the quizzes (each quiz is worth 10 points).

There will be an exercise sheet for each week, except when there is a quiz of which there will be two: a midterm and a final quiz.

There is no provision for repeated attempts at obtaining a course credit from the tutorial.

Students must obtain the credit from a tutorial before taking the exam.

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: doc. RNDr. Vít Jelínek, Ph.D. (11.10.2017)

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 |