یک رنگ‌آمیزی راسی برای گراف $G$، به معنای نسبت دادن تعدادی عدد طبیعی به رئوس $G$ است، به طوری که به هر دو راس مجاور اعداد نامساوی نسبت داده شود. برای گراف $G$، رنگ‌آمیزی درستی که در آن مجموع رنگ‌ها کمینه باشد را در نظر بگیرید. این مجموع را با $S(G)$ نشان می‌دهیم. ثابت کنید، $S(G)$ از مجموع تعداد یال‌ها و رئوس $G$‌بیش‌تر نیست.

• سوال بعد
• سوال قبل