گراف جهت‌دار ‎$G$‎ به این صورت داده شده است که درجه‌ی خروجی هر راسش ‎$k$‎ است. برای هر دو راس ‎$u$‎ و ‎$v$‎ تعداد یال‌ها از ‎$u$‎ به ‎$v$‎ از یک بیشتر نیست، اما ممکن است هم از ‎$u$‎ به ‎$v$‎ و هم از ‎$v$‎ به ‎$u$‎ یال داشته باشیم. ثابت کنید اگر ‎$k > \lfloor n/2 \rfloor n/2$‎ باشد، ‎$G$‎ حتماً دور به طول ‎۳‎ دارد و اگر ‎$k \leq \lfloor n/2 \rfloor n/2$‎ باشد، ‎$G$‎ ممکن است دور به طول ‎۳‎ نداشته باشد.

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