گراف ساده و 𝑛 رأسی 𝐺 را با این شرط در نظر بگیرید که دور همیلتونی(دور به طول 𝑛) دارد و 𝑇 یک زیردرخت فراگیر آن است (یعنی زیرگرافی 𝑛 رأسی که درخت باشد.) 𝐹(𝐺,𝑇) را کمینه‌ی تعداد یال‌هایی از 𝐺 در نظر بگیرید که باید به درخت 𝑇 اضافه کنیم تا درجه ی هر رأس آن حداقل ۲ شود.

مقدار 𝑝(𝑛) را برابر بیشینه‌ی مقدار 𝐹(𝐺,𝑇) به ازای همه ی گراف‌های 𝑛 رأسی 𝐺 (با شرایط گفته شده) و همه‌ی زیر درخت‌های فراگیر 𝑇 از 𝐺 تعریف می‌کنیم. مقدار 𝑝(𝑛) به ازای 𝑛≥۳ چند است؟

توضیح: برای پاسخ لازم است ابتدا مقدار مورد نظر خود را بر حسب 𝑛 بیان کنید (۲نمره)، سپس به ازای هر 𝑛 مثالی بزنید که مقدار بیشینه را داشته باشد (۸نمره) و نهایتاً نشان دهید 𝐹(𝐺,𝑇) برای هر گراف 𝑛 رأسی 𝐺 (با شرایط گفته شده) و هر زیردرخت فراگیر 𝑇 از 𝐺 از مقدار 𝑝(𝑛) مورد نظر شما بیشتر نمی‌شود.(۱۴نمره).

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