Syllabus
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.
Annotation
The lecture extends NDMI011. An overview lecture on classical results in combinatorics and graph theory.