====== سوالات ۱۴ و ۱۵ ======


یک گراف ساده را
**سلطانی**
گوییم، اگر اختلاف درجه‌ی هیچ دو رأس آن برابر یک نباشد. برای مثال گراف زیر سلطانی نیست، زیرا هم رأس با درجه‌ی یک و هم رأس با درجه‌ی دو دارد:
{{ :سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۷:p16-1.png?200 |}}
توجه کنید  در یک گراف سلطانی، وجود دو رأس با درجه‌ی برابر مشکلی ندارد. برای مثال، گراف زیر سلطانی است:
{{ :سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۷:p16-2.png?200 |}}


====== سوال ۱۴ ======


یک گراف ساده‌ی ۱۱ رأسی سلطانی داریم که کامل نیست.  این گراف حداکثر چند یال دارد؟

  - ۴۹
  - ۵۳
  - ۵۲
  - ۴۵
  - ۵۴


<پاسخ>
گزینه (۳) درست است.


اگر گراف تنها یک یا دو یال از 
$\binom{11}{2}$
یال موجود را نداشته باشد، هم رأس با درجه‌ی ۱۰ و هم رأس با درجه‌ی ۹ خواهد داشت. پس حداکثر 
$\binom{11}{2} - 3 = 52$
یال داریم. حال یک گراف کامل ۱۱ رأسی در نظر بگیرید که یک مثلث از یال‌های آن پاک شوند. این گراف ۳ رأس با درجه‌ی ۸ و ۸ رأس را درجه‌ی ۱۰ دارد که معتبر است.

</پاسخ>



====== سوال ۱۵ ======

یک گراف ساده‌ی ۱۱ رأسی سلطانی داریم. در این گراف هیچ سه رأسی وجود ندارد که دو به دو به هم وصل باشند. این گراف حداکثر چند یال دارد؟

  - ۲۶
  - ۲۹
  - ۲۸
  - ۲۷
  - ۳۰ 


<پاسخ>
گزینه (۳) درست است.



ابتدا ثابت می‌کنیم تعداد یال‌ها نمی‌تواند از ۲۸ بیش‌تر باشد. طبق قضیه‌ی منتل یک گراف $n$ رأسی فاقد مثلث، نمی‌تواند بیش از 
$\lfloor \frac{n^2}{4} \rfloor$
یال داشته باشد (اثبات این قضیه را می‌توانید در کتاب‌های گراف بیابید).
دو حالت داریم:

  * گراف، دور به طول فرد دارد: فرض کنید طول کوچک‌ترین دور به طول فرد برابر $2l+1$ باشد. رأس‌های این دور، یالی به جز یال‌های خود دور به هم ندارند (زیرا در غیر این صورت دوری به طول کم‌تر و فرد خواهیم داشت).  هر رأس خارج دور، حداکثر به $l$ رأس از دور وصل است (زیرا در غیر این صورت مثلث تشکیل می‌شود). $11-(2l+1)=10-2l$ رأس دیگر نیز حداکثر $\lfloor \frac{(10-2l)^2}{4} \rfloor = \frac{(5-l)^2}{4}$ یال بین خود دارند. پس گراف دارای حداکثر $$(2l+1)+(10-2l)\times l + (5-l)^2$$ یال است. مقدار $l$ می‌تواند ۱، ۲، ... یا ۵ باشد. با گذاشتن این مقادیر در عبارت بالا، حداکثر ۲۷ یال خواهیم داشت.
  * گراف دور به طول فرد ندارد: پس گراف دوبخشی است. اگر یک بخش آن حداکثر چهار رأس داشته باشد، حداکثر ۲۸ یال خواهیم داشت. حال گراف دوبخشی کامل با بخش‌های پنج و شش رأسی را در نظر بگیرید. با حذف حداکثر یک یال از این گراف، هم رأس با درجه‌ی پنج و هم رأس با درجه‌ی شش خواهیم داشت؛ پس در هر صورت گراف ما دست کم ۲۸ یال دارد.
</پاسخ>



  * [[سوالات ۱۲ و ۱۳|سوال قبل]]
  * [[سوالات ۱۶ و ۱۷|سوال بعد]]