نفر دوم میتونه ببره اگر در این گراف تطابق کامل وجود داشته باشه ( منظورم از تطابق کامل تطابقیه که همه رئوس رو شامل بشه ، البته قبلش باید بدونید تطابق چیه )

استقرا میزنیم به این صورت که فرض میکنیم به ازای k - 2 راس اگر گراف تطابق کامل داشته باشه نفر دوم میبره و حکممون هم اینه که به ازای k راس اگر گراف تطابق کامل داشته باشه نفر دوم برندست. ( k باید مقداری زوج باشه )

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

در حالت k راس وقتی نفر اول اولین راس به اسم v رو انتخاب کرد ، چون این راس توی تطابقمون اومده پس حداقل به یه راس دیگه به اسم u یال داره ( یال u v توی تطابق وجود داره)

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

حالا میشه گفت طبق فرض استقرا در گرافی با k -2 راس که شامل تطابق کامله حتمن نفر دوم میبره. و حکم ثابته . چون نفر دوم توی حالت k راس همون نفر دوم توی حالت k - 2 راسه. پس وقتی توی حالت k -2 نفر دوم ببره توی حالت k هم نفر دوم میبره.

نتیجه ای که میشه گرفت اینه که اگر گراف حداقل یک مولفه داشته باشه که تطابق کاملی توش نباشه در اون صورت نفر اول برندست. برای اثباتش مییایم بزرگترین تطابق توی مولفه ی مورد نظر رو در نظر میگیریم اسم این تطابقو میذاریم H . میدونیم راس y در اون مولفه وجود داره به طوری که توی H نیومده. نفر اول y رو انتخاب میکنه . حالا نفر دوم به ناچار راسی مجاور با y به نام w رو انتخاب میکنه میدونیم w حتمن توی H اومده . چون اگر نیومده بود یال y w رو میتونستیم جزئی از H بدونیم ( چرا ؟ ...... چرا نه ؟ ) از طرفی میدونیم H بزرگترین تطابق ممکن توی این مولفست پس امکان نداره بزرگتر از این بشه .
خب پس w حتمن توی H اومده . ( به شکل نگاه کنید )

بعد نفر اول با حرکت روی یال های H هر بار توی نوبت خودش یکی از رئوس مجموعه قرمز رو انتخاب میکنه . این در صورتی ممکنه که نفر دوم همیشه توی نوبت خودش یه راس از مجموعه آبی رو انتخاب کنه . اینو ثابت میکنیم که اگر نفر دوم راسی از مجموعه سیاهو انتخاب کنه سایز H بیشتر میشه و تناقض پیش میاد . توضیح این موضوع یکم سخته برای همین ممکنه چیزی از توضیحام سر در نیارید .

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

میدونیم در حالت کلی خطوط صاف جزو H هستند ولی اگر خطوط صاف رو دور بریزیم و یال های H رو خطوط مورب در شکل بالا فرض کنیم متوجه میشویم که سایز H افزایش یافته و این تناقض است . پس تنها یک راس از مجموعه سیاه انتخاب میشود و آن هم اولین راس یعنی y است .

پس نفر اول در حالتی که یک مولفه تطابق کامل نداشته باشه میبره و اینا .
فکر نکنم بشه راحت تر از این توضیح داد ولی اگر کسی اثبات کم حجم تری بلده لطفن ارائه بده .