سلام
میدانیم طبق اصل لانه کبوتری در یک گراف حد اقل دو راس با درجه یکسان وجود دارد ( چرا ؟ چون اگر N راس داشته باشیم ، درجه هر راس میتوانید عددی از صفر تا N - 1 را باشد . اگر بنا باشد که هیچ دو راسی درجه یکسان نداشته باشند پس راسی با درجه صفر و نیز راسی با درجه N - 1 خواهیم داشت که تناقض است )

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

دو راس v و u را حذف میکنیم . در این صورت در گراف باقیمانده میتوان فرض استقرا رو پیاده سازی کرد ( فرض استقرا میگه گرافی با k یال حتمن دو راس مطلوب داره ، بر روی تعداد یالها استقرا زدیم )

حال که دو راس مطلوب طبق فرض استقرا بدست اوردیم ، u و v را دوباره به گراف اضافه میکنیم ، میدانیم همچنان آن دو راس ، مطلوبیت خود را حفظ میکنند (!) و درجه شان همچنان با هم برابر است ( چون درجه هر دو راس +1 میشود ).

پ ن : برای پایه استقرا به اضای e = 0 داریم » دو راس درجه صفر را در نظر میگیریم » این دو راس هم درجه یکسانی دارند و هم راس سومی وجود دارد که به هردوشان یال ندارد.

پ . ن 2 : میشد روی رئوس هم استقرا زد ولی روی یال هاش هم درست بود ... نبود ؟