Notes on Cambridge Maths

Something looks off?

The button will add this page to my log of things to fix. Use it for broken links, equations not rendering correctly, etc.
Submit other issues on GitHub.

Greedy Colouring

Proposition

Let be a Graph. Then:

Proof

Greedy

Proposition

Let be a connected graph and . Then:

Proof

Order vertices of into such that:

  • is connected to
  • is connected to at least one of
    (take it as BFS)
    Now every vertex has less than edges towards for
    Thus a greedy colouring works.

Something looks off?

The button will add this page to my log of things to fix. Use it for broken links, equations not rendering correctly, etc.
Submit other issues on GitHub.

Graph View

Backlinks