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

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