احتمالن هدف نویسنده رسوندن این سواله : که ما یه گرافی داریم که به ازای هر دو راس متمایز $u, v$ داریم $d_u + d_v > n$. ثابت کنید که این گراف دور همیلتونی داره! ($d_v$ یعنی تعداد همسایه های راس $v$)

در جای جای راه حل از اینکه تعداد رئوس گرافه بیشتر از ۲ هست استفاده میکنیم! (چون کمتر باشه اون خاصیت رو نخواهد داشت.)

برهان خلف میزنیم... بزرگترین (پریال ترین) گراف $n$ راسی که خاصیت صورت مسئله رو داراست ولی دور همیلتونی نداره رو در نظر میگیریم. این گراف کامل نیست چون گراف کامل حتمن دور همیلتونی داره! (هر جایگشت دلخواهی از رئوس یه دور همیلتونیه) پس حتمن جفت راس $u, v$ وجود دارند که بینشون یالی نیست. چون که این گراف بزرگترین در نوع خودشه ، حتمن با اضافه کردن یال $uv$ یک دور همیلتونی بوجود میاد.(اگه بوجود نیاد یه گراف بزرگتر با خواص گفته شده داریم که با فرضمون در تناقضه.)

چون این دور قبل از اضافه کردن یال $uv$ وجود نداشت حتمن شامل اون یال میشه. پس با حذف کردن اون یال ما یک مسیر $n$ راسی داریم که دو سرش رئوس $v, u$ هستند و در گراف اصلیمون وجود دارند. خب این مسیر رو در نظر میگیریم. اگه دو راس پشت سر هم در مسیر وجود داشته باشند که وضعیتشون مثل شکل زیر باشه (اونی که تو مسیر به $u$ نزدیک تره همسایه ی $v$ باشه و اونی که تو مسیر به $v$ نزدیک تره همسایه ی $u$ باشه) میشه مثل شکل با جدا کردن یال بین اون دو همسایه و وصل کردن به دو سر مسیر یک دور همیلتونی درست کرد و این با فرضمون که این گراف دور همیلتونی نداره در تناقضه.

خب پس حالا بیاین مجموع همسایه های $v, u$ رو بشمریم! بدون هیچ فرض اضافه این دو راس حداکثر میتونن $2n-2$ همسایه داشته باشن (چون درجه ی هر راس حداکثر $n-1$ هست! ) ولی چون وضعیت گفته شده هم وجود نداره، به ازای هر همسایه ی $v$ ، یکی از امکانات برای همسایگی $u$ از بین میره .(و برعکس) (چون به ازای هر همسایه ی $v$ ، راس سمت راستیش نمیتونه به $u$ وصل بشه!) پس در مجموع حداکثر $n-1$ همسایه دارند و این با فرض کلی مسئله در تناقضه پس از اول اون فرض که چنین گرافی وجود داره غلط بوده! $^_^$

پ.ن. این کافیه که هر دو راسی مجموع درجاتشون حداکثر $n$ باشه ... بنظر میرسه که لزومی نداره از $n$ بیشتر باشه!