Graf možemo uvek obojiti na pravilan način pod navedenim uslovima:

Posmatrajmo sve čvorove koji imaju više ili jednako od ~1000~ grana, takvih čvorova ima najviše ~\frac{n}{1000} \leq \frac{300000}{1000} = 300~. Njih možemo obojiti u prvih ne više od ~300~ boja sigurno.

Svi ostali čvorovi imaju manje od ~1000~ grana, što znači da će takvi čvorovi biti povezani sa najviše ~999~ drugih obojenih čvorova - ostaju nam dve boje koje nismo iskoristili i uvek jednu možemo iskoristiti za naš trenutni čvor.

Konačan algoritam možemo implementirati na identičan način (prvo bojenjem čvorova sa više od ~1000~ grana, i nakon toga svih ostalih).

Postoji i mnogo drugih ideja kako možemo realizovati bojenje.