discipline 
Mathematics, Applied
mathematics

subject 
Graph theory

lecturers 
András Frank 
credits 

period 
1 or 3 
curriculum 
Basic techniques: algorithmic proofs, separation
along tight sets, the splitting off operation, the uncrossing technique.
Perfect graphs and Lovasz' perfect graph theorem.
Theorems of Kuratowski (planar graphs), Tutte (3connected graphs), Brooks (colouring), Tutte (perfect matching),
Edmonds (disjoint arborescences), Tutte (disjoint trees).
Orientation theorems (Robbins, NashWilliams). Splitting theorems of Lovasz and Mader. Undirected
edgeconnectivity augmentation by Watanabe and Nakamura and its directed
counterpart. Theorem of Lucchesi and Younger. Konig's edgecolouring theorem. Stable matchings and
Galvin's list colouring theorem. Edgedisjoint paths (RothschildWhinston, LovaszCherkassky.) 
literature 

form of tuition 
Lectures 
mode of assessment 
written/oral
exam 