Let have two nonadjacent neighbours in a finite graph , with connected. Then . Give one common colour. In a spanning tree of the remaining graph rooted at , order vertices from larger to smaller distance from the root and colour greedily in that order. Every vertex before has an uncoloured parent, so at most colours are forbidden there. At , the two initial neighbours use the same colour, so again at most distinct colours are forbidden. This constructs a proper colouring from a palette of colours. It is a useful local step in Brooks' theorem.

Articles by others on the same topic (0)

There are currently no matching articles.