Combinatorics

Summary.

• Vizing's Theorem

• Brooks' Theorem

• graphs are bipartite if and only if they contain no cycle of odd length

• Ramsey's Theorem

• graphs are bipartite if and only if they are \(2\)-colourable

• Petersen graph

• Important definitions:

  • edge-colouring, proper edge-colouring

  • edge-chromatic number

  • bipartite, bipartition

  • complete bipartite graph

  • proper \(k\)-colouring, \(k\)-colourable

  • chromatic number

• Notation:

  • \(\displaystyle \chi'(G)\)

  • \(\displaystyle K_{m,n}\)

  • \(\displaystyle R(n_1, \ldots, n_c)\)

  • \(\displaystyle \chi(G)\)