با اکسترمال هم همیشه

یه گراف کامل رو در نظر میگیریم و فرض میکنیم راس a بیشترین درجه خروجی(برد) رو داره(مستقیم یا باواسطه)

بعد برهان خلف میزنیم و میگیم این پادشاه حداقل از 1 نفر باخته(بهش راه نداره) و فرض میکنیم از راس b باخته

بعد میگیم اگر بخوایم a از b باخته باشه پس b باید از تمام کسانی که a ازشون مستقیم برده،برده باشه تا به a راه پیدا نکنه پس تا الان درجه خروجی b برابر$d(a) $است

ولی چون راس a از b مستقیما هم باخته پس به درجه خروجی b یکی اضافه میشه یعنی تعداد برد هاش از a بیشتر میشه که تناقضه

پس ثابت شد:)

ثابت میکنم اگه هیچ کس همه ی افرادو نداشته باشه حداقل دوتا پادشاه!! داره!

طبق اون قضیه ی معروف یدونه داره! حالا اون راسایی که اینو بردن خودشون یه کینگ دارن! ثابت میکنم اون کینگه کینگ کل گراف هم هست!

تو دسته ی خودش که کینگه! کینگ اول رو مستقیم برده! پس بقیه رو هم با یه واسطه(کینگ اول) برده پس کینگه!

حکم را با استقرا روی $n$ (تعداد راس های تورنمنت ( گراف کامل جهت دار )) ثابت می کنیم ،

حکم به ازای $n=2 $ برقرار است ، یعنی نفری که برده است جایزه می گیرد .

فرض کنید حکم به ازای $n$ درست باشد یعنی در 1 تورنمنت $n$ راسی تنها یک شخص وجود دارد که جایزه گرفته و آن فرد هم همه افراد را برده است ، حال یک تورنمنت $n+1$ راسی در نظر بگیرید و راسی دلخواه را از آن حذف کنید ، ( راس را $v$ بنامید ) طبق فرض استقرا در میان $n$ راس بافیمانده راسی داریم که از همه برده است ( آن را $u$ بنامید )

1)اگر $u$ از $v$ برده باشد آنگاه قطعا تنها $u$ جایزه می گیرد که همه را برده است و $v$ جایزه ای نمی گیرد چرا که در هر حالتی $v$ از $u$ باخته است (حتی با واسطه ) چرا که هیچ راس دیگری وجود ندارد که $v$ از آن برده باشد و راس مذکور از $u$ برده باشد (همه راس ها از $u$ باخته اند) برای سایر رئوس هم به همین شکل می توان گفت شرایط را ندارند .

2)اگر $v$ از $u$ برده باشد ، آنگاه چون در فرض سوال گفته شده که به دو نفر جایزه تعلق نمی گیرد قطعا $v$ همه راس ها را برده است برهان خلف می زنیم اگر راسی داشته باشیم که $v$ از آن باخته است چون $u$ قطعا راس مذکور را برده و راس مذکور هم $v$ را برده پس $u$ جایزه می گیرد اما در این حالت $v$ هم جایزه می گیرد چون $u$ را برده و $u$ هم همه راس ها را برده است که پس $v$ جایزه می گیرد که یعنی 2 جایزه که با فرض در تناقض است پس $v$ همه راس ها را برده و تنها کسی است که جایزه را برده است ( بدیهی است که هیچ راس دیگری نیز نمی تواند جایزه بگیرد چون قطعا همکی در هر حالتی از $v$ باخته اند )

پس حکم به ازای $n+1$ هم برقرار است .