گراف زیبا (۲۰ نمره)

به یک گراف «زیبا» می‌گوییم، اگر همه‌ی شرایط زیر را داشته باشد:

• ساده باشد.
• تعداد رأس‌های آن $2025$ باشد.
• هر دور آن دقیقاً $4$ رأس داشته‌ باشد.

الف) فرض کنید $G$ یک گراف زیبا باشد. ثابت کنید می‌توان یک یال به $G$ اضافه کرد، طوری که گراف حاصل ساده بماند و طول بزرگ‌ترین دور آن از $4$ بیش‌تر نشود. (۱۴ امتیاز)

ب) یک گراف زیبای $G$ ارائه دهید که با اضافه کردن هم‌زمان هر دو یالی به $G$، گراف حاصل حداقل یکی از دو شرط زیر را داشته باشد: (۶ امتیاز)

1. گراف حاصل ساده نباشد.
2. طول بزرگ‌ترین دور گراف حاصل از $4$ بیش‌تر باشد.