سوال ۲

اگر ۴ راس داشته باشیم، پاسخ چیست؟ اگر ۳ راس اضافه شوند چه؟

مثال را با نمونه گیری از حالات بالا و اتصال تعدادی «لوزی» به هم بسازید.

تعریف دقیق گراف چنین خواهد بود. راس‌های $a_1, a_2, \dots, a_{333}$ را تعریف می‌کنیم. حال برای هر $i$ از ۱ تا ۳۳۲، راس $b_i$ و $c_i$ را تعریف می‌کنیم. $b_i$ را به $a_{i-1}$ و $a_i$ متصل می‌کنیم و $c_i$ را مشابه $b_i$.

فرض کنید گراف یال برشی نداشته باشد. سعی کنید حکم را ثابت کنید.

برای اثبات گزاره‌ی راهنمایی فوق، روی گراف الگوریتم BFS را اجرا کنید.

چون گراف یال برشی ندارد، بین هر دو ارتفاع از BFS حداقل دو یال وجود دارد.

پس دو ارتفاع متوالی وجود ندارند که هر دو شامل دقیقا ۱ راس باشند.

پس بیشینه‌ی ارتفاع درخت BFS برابر $\left\lfloor \frac{2(m-1)}{3} \right\rfloor$ خواهد بود.

حال از این مسئله در سوال اصلی استفاده کنید.

یال‌های برشی را از گراف حذف کنید.

به کمک راه حلی که برای گراف‌های بدون یال برشی یافتیم، از هر راس هر مؤلفه می‌توانید به هر راس دیگرش بروید. سپس بین مؤلفه‌ها جابه‌جا شوید تا به مقصد برسید.