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

برای رأس $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)$ خواهد بود.