استقرا میزنیم رو تعداد راسای گرافه!
پایه رو میذاریم همه ی گراف هایی که توشون درجه همه راساشون زوجه. همه گرافو میذاریم تو یه دسته!
گام: الان گراف $G$ رو داریم که راسی درجه فرد بنام $v$ داره. میایم گراف $G'$ رو اینجوری میسازیم: راس $v$ رو حذف میکنیم و یال های بین همسایه های $v$ رو هم چپه میکنیم؛ یعنی یال بین راسای $a, b \in N(v)$ در $G'$ وجود داره اگر و تنها اگر تو $G$ وجود نداشته باشه.
حالا طبق فرض استقرا میدونیم راسای $G'$ رو میشه به دو دسته مطلوب افراز کرد، این دو دسته کردن رو در نظر میگیریم. یال های بین راسایی که تو $G$ با $v$ همسایه بودن رو به حالت اولیشون برمیگردونیم. این راسا تعدادشون فرد تاست، پس تو یکی از این دو دسته زوج تاشون اومده و تو یکی فرد تاشون. $v$ رو هم به دسته ای اضافه میکنیم که توش زوج تا همسایه داره!
الان 4 جور راس داریم:

1. راسای بجز $v$ و $N(v)$: خب اینا تو $G'$ تو دسته خودشون زوج تا همسایه داشتن، الانم تغییری رخ نداده براشون پس هنوزم در دستشون زوج همسایه دارن.

2. اون فرد تا راس از $N(v)$ که هم دسته بودن: زوجیت درجشون بین خودشون که تغییر نمیکنه؛ پس اینا هم الان زوج همسایه تو دستشون دارن.

3. اون زوج تا راس از $N(v)$ که هم دسته بودن: اول با تغییر دادن یالای بینشون زوجیت درجشون عوض میشه و بعدش با اضافه کردن $v$ که با همشون همسایست، دوباره زوجیت درجشون تو دستشون به همون حالت اولیه (زوج) برمیگرده!

4. $v$: خب به اون دسته ای اضافه کردیم که زوج همسایه توش داشت دیگه، پس اونجا زوج همسایه داره! D: