سوال ۳

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

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