یک گراف ساده‌ی جهت‌دار ‎$n$ رأسی داریم که درجه‌ی خروجی هر رأس در آن، دست کم ‎$\frac{n}{3}$‎ است. ثابت کنید در این گراف، ‎$C_3$‎ جهت‌دار یا ‎$C_4$‎ جهت‌دار وجود دارد‎.

توجه: می توانید فرض کنید در گراف ما، علاوه بر این که درجه‌ی خروجی هر رأس، دست کم ‎$\frac{n}{3}$‎ است، درجه‌ی ورودی هر رأس نیز، دست کم ‎$\frac{n}{3}$‎ باشد و نیمی از نمره را بگیرید.

• سوال قبل