سلام :)

استقرا میزنیم روی $n$ : پایه: پایه رو پاین نوشتم ، فرض : برای $n$ درسته برای $n+1$ میخوایم ببینیم درسته یا نه!

خب اگه توی این $m$ راس ، راسی به نام $u$ باشه که به حداقل $p=m-n-1$ راس متصل باشه : اون وقت ما توی این p هر $n$ تا راسی که بگیریم و راس $u$ رو بگیریم (در مجموع $n+1$ راس) باید دو راس باشد که بینشان یالی نباشد چون حتما یکی از این دو راس $u$ نمی باشد پس این دو راس از مجموعه رئوس $P$ است پس هر $n$ راس از $P$ را بگیریم دو راس هست که بینشان یالی نیست خب پس رو $P$ استقرا میزنیم $P$ حداکثر $ \frac{(n-1).(n+2)}{2}$ راس دارد پس در مجموع m حداکثر $\frac{(n-1).(n+2)}{2} + n+1 = \frac{n.(n+3)}{2}$ راس دارد .

در غیر این صورت راسی به نام $v$ هست که به حداقل n+1 راس متصل نباشد هر دو تا از اون $n+1$ راس به نام های $p,q$را که بگیریم (چون بین $u$ و $p$ , $q$ یالی نیست پس طبق شرط اول مسئله باید یه یال بین $p$, $q$ باشه ) بهم متصل اند پس یک گراف $k_{n+1}$ راسی داریم که با شرط دوم مسئله در تناقض است$\ast $ .

پایه : فرض کن $n=3$ باشد میخوایم بگیم m حداکثر 5 است یعنی بگیم 6 نمی تونه باشه بعد برای 5 مثال میزنم پس یه راس به نام $u$ بگیر .

1. اگه درجه $u$ از 3 بیشتر یا مساوی بود هر دوتایی که از اون رئوس (متصل بهش) رو که بگیریم بینشون یالی نست که با شرط اول مسئله در تناقش است .
2. پس درجش از 3 کمتره پس بیش از 3 راس هستن که بهش متصل نیستند پس هر دو راسی رو که بگیریم بینشون یاله پس باز نیز گراف $k_{3} $ دارد که با شرط دوم در تناقش است .

مثالی برای 5 :

نیازی به توضیح مثال هم هست ؟