Untuk batas atas, kita dapat memperbaiki batas “jumlah simpul” dengan memperhatikan derajat simpul. Misalkan \(\Delta(G)\) menyatakan derajat terbesar dari semua simpul dalam graf \(G\text{.}\) Dugaan yang wajar untuk batas atas bilangan kromatik adalah \(\chi(G) \le \Delta(G) + 1\text{.}\) Mengapa dugaan ini wajar? Mulai dari sembarang simpul, simpul tersebut beserta semua tetangganya selalu dapat diberi \(\Delta(G) + 1\) warna, karena himpunan ini memuat paling banyak \(\Delta(G) + 1\) simpul. Sekarang, perluas pewarnaannya! Pada setiap tahap, jika Anda meninjau simpul yang telah diwarnai, sebagian tetangganya mungkin telah diwarnai dan sebagian lainnya belum. Namun, dalam keadaan apa pun, simpul tersebut dan semua tetangganya dapat diberi warna berbeda, karena terdapat paling banyak \(\Delta(G)\) tetangga, ditambah satu simpul yang sedang ditinjau.