درختی ‎$n$‎ راسی داده شده‌است. می‌خواهیم یال‌های آن را طوری جهت‌دهی کنیم که درجه‌ی خروجی هیچ دو راس مجاوری برابر نباشد‎.

1. ثابت کنید می‌توان طوری اینکار را انجام داد که درجه‌ی خروجی هر راس حداکثر برابر با $4$ باشد.‎
2. درختی ارائه دهید که درجه خروجی ماکسیمم در آن با شرایط گفته شده حداقل ‎$3$‎ باشد.
3. درختی ارائه دهید که درجه خروجی ماکسیمم در آن با شرایط گفته شده حداقل ‎$4$‎ باشد.

• سوال قبل