فرض کنید رئوس گراف را به ترتیبی دلخواه روی یک خط چیده‌ایم و آنها را از چپ به راست مطابق با روش زیر رنگ می‌کنیم:

برای رأس ‎$v$‎ مجموعه‌ی ‎$A$‎ را مجموعه‌ی رنگهای رئوسی که همسایه‌ی ‎$v$‎ هستند و تا به حال رنگ شده‌اند در نظر بگیرید. رنگ رأس ‎$v$‎ برابر است با کم‌ترین عدد طبیعی که در مجموعه‌ی ‎$A$‎ وجود ندارد‎.

‎ با این روش رنگ‌آمیزی تعداد رنگ‌های مورد نیاز حداکثر ‎$\bigtriangleup‎ + ‎1$‎ است. زیرا به ازای هر رأس، مجموعه‌ی ‎$A$‎ حداکثر ‎$\bigtriangleup$‎ تا عضو دارد و بنابراین رنگ هر رأس حداکثر برابر ‎$\bigtriangleup‎ + ‎1$‎ می‌شود‎.

‎ این الگوریتم درصورتی که ‎$\bigtriangleup$‎ زوج باشد، مورد قبول است، زیرا در این صورت ‎$k$‎ برابر ‎$\bigtriangleup‎ +‎1$‎ می‌شود و ما می‌توانیم گراف را با ‎$k$‎ رنگ، رنگ آمیزی کنیم. اما در صورتی که ‎$\bigtriangleup$‎ فرد باشد، ‎$k$‎ برابر خود ‎$\bigtriangleup$‎ می‌شود و این روش مورد قبول نیست. اما اگر در این روش کاری کنیم که به ازای هر رأس اندازه‌ی مجموعه‌ی ‎$A$‎ حداکثر ‎$k-1$‎ شود، آنگاه می‌توانیم مطمئن باشیم که حداکثر از ‎$k$‎ رنگ استفاده کرده‌ایم. برای این کار کافی است ترتیبی از رأس‌ها ارائه دهیم که در آن به ازای هر رأس حدکثر ‎$k-1$‎ تا از همسایه‌هایش در سمت چپش قرار داشته باشد.

درحالتی که ‎$\bigtriangleup$‎ فرد است، چون تعداد رئوس هم فرد است، حداقل یک رأس وجود دارد که درجه‌ی آن از ‎$\bigtriangleup$‎ کم‌تر باشد.اسم این رأس را ‎$u$‎ می گذاریم.

درخت ریشه داری را درنظر بگیرید که ریشه‌ی آن رأس ‎$u$‎ باشد. اگر ترتیب رئوس در الگوریتم بالا، به ترتیب عمق رئوس در این درخت باشد (از پایین به بالای درخت)، به جز ریشه درخت که رأس ‎$u$‎ است، بقیه‌ی رئوس حداقل یک همسایه (پدر آن رأس در درخت ریشه دار) در سمت راست خود دارند. رأس ‎$u$‎ هم حداکثر ‎$\bigtriangleup‎ -‎1$‎ همسایه دارد. بنابراین هر رأس در سمت چپ خود حداکثر ‎$\bigtriangleup‎ -‎1$‎ یال دارد. پس اگر الگوریتم بالا را با این ترتیب از رأس‌ها اجرا کنیم، حداکثر ‎$\bigtriangleup$‎ رنگ استفاده خواهد شد‎.‎

پيچيدگي

الگوریتم رنگ‌آمیزی که در ابتدا مطرح شد درصورتی که برای نگهداری گراف از لیست مجاورت استفاده شود از ‎$O(e)$‎ است، زیرا در آن، هر رأس و لیست همسایه‌هایش دقیقا یک بار بررسی می‌شود. در صورتی که ‎$\bigtriangleup$‎ فرد باشد، باید قسمت دوم الگوریتم که ارائه‌ی ترتیبی از رئوس برحسب درخت ریشه‌دار است نیز اجرا شود. این قسمت نیز می‌تواند با استفاده از یکی از الگوریتم‌های ‎BFS‎ یا DFS پیاده سازی شود که هر دو از ‎$O(e)$‎ هستند. بنابراین کل الگوریتم از ‎$O(e)$‎ خواهد بود.