می‌دونیم همه ماها تو اصل هشتی

ابتدا مثالی که حداقل ۳ رنگ نیاز داشته باشد بزنید.

کافیست یک دور هفت راسی و ۲۳ راس تنها در نظر بگیرید.

نشان دهید هر چنین گرافی ۴ رنگ پذیر است.

زیرگراف مینیمال $H$ از $G$ را در نظر بگیرید که ۵ رنگ پذیر باشد. این زیرگراف، ۵-بحرانی است. یعنی حذف هر راس از آن، زیرگراف را ۴ بحرانی می‌کند.

نشان دهید $\delta(H) \ge 4$

در صورت درست نبودن گزاره‌ی راهنمایی فوق، به استقرا نشان دهید $H$ چهار رنگ‌پذیر است.

نشان دهید $H$ راسی با درجه‌ی حداقل ۵ دارد.

برای گزاره‌ی لم قبل از قضیه‌ی بروکس $(Brooks)$ استفاده کنید.

راس با درجه‌ی ۵ را $x$ و همسایه‌ی دلخواهی از آن را $y$ بگیرید. تعداد راس‌های $H$ را بر اساس $x$ و $y$ بشمارید.

دقت کنید به دلیل نداشتن دور به طول‌های ۳، ۴ و ۵، راس‌هایی که از یال $xy$ فاصله‌ی ۱ یا ۲ دارند باید متمایز باشند.

راس $x$ دارای ۴ همسایه غیر از $y$ است که هر یک، ۳ همسایه‌ی دیگر نیز دارند.

راس $y$ حداقل ۳ همسایه‌ی غیر از $x$ دارد که هر یک، حداقل ۳ همسایه‌ی دیگر نیست دارند.

چون دوبه‌دوی راس‌های بالا باید متمایز باشند (به دلیل شرط مسئله روی طول دور‌ها) پس $H$ دقیقا ۳۰ راس دارد.

ثابت کنید $H$ دو بخشی است. از شرط طول دور‌ها استفاده کنید.

یک بخش را $x$، همسایه‌های $y$ و رئوسی که از $y$ فاصله‌ی ۲ دارند بگیرید. باقی را در بخش دیگر قرار دهید. با ۵-بحرانی بودن $H$ به تناقض رسیده‌ایم.