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

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

  * [[سوال ۶|سوال بعد]]
  * [[سوال ۴|سوال قبل]]