Matching and covering: Matching in bipartite graphs - Konig's theorem, Hall's marriage theorem. Matching in general graphs - Tutte's theorem. Path covers - Gallai-Milgram theorem, Dilworth theorem.
Connectivity: The structure of 2-connected graphs, structure of 3-connected graphs, Menger's theorem.
Planar graphs: Euler's formula, Wagner's theorem, Kuratowski's theorem.
Colouring: Five colour theorem for planar graphs, vertex colouring - Brooks' theorem, Edge colouring - Vizing's theorem.