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.