یک گراف ‎«چهاررنگ‌پذیر رأسی»‎ است اگر و فقط اگر بتوان به هر رأس آن، یکی از اعداد ‎$1$‎، ‎$2$‎، ‎$3$‎ یا ‎$4$‎ را نسبت داد به طوری که عدد دو سر هیچ یالی یک‌سان نباشد.

گراف ‎$G$‎ با ‎$e$‎ یال داده شده است. ثابت کنید که می‌توان ‎${\lceil {3e \over 4} \rceil}$‎ از یال‌های ‎$G$‎ را انتخاب کرد به طوری که زیرگراف حاصل از این ‎$\lceil {3e \over 4} \rceil$‎ تا یال، چهار رنگ پذیر رأسی باشد.

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