Combinatorics

Summary.

• Kuratowski's Theorem, Wagner's Theorem

• Euler's Formula

• \(|E|\le 3|V|-6\) for a planar graph

• colouring maps

• the Five Colour Theorem

• the Four Colour Theorem

• Important definitions:

  • planar graph, planar embedding

  • face

  • dual graph, planar dual

  • subdividing an edge, subdivision of a graph

  • edge contraction, contracting an edge

  • minor

  • cubic graph

  • bridge

  • snark