حکم را قوی می‌کنیم، شرط هم‌بند بودن گراف را بر می‌داریم.

روی مجموع تعداد راس‌ها و یال‌ها (n + k) استقرای قوی می‌زنیم. برای n + k = 1 درست است، چرا که هیچ راسی وجود ندارد که بیش‌تر از ۱ یال از آن گذشته باشد، که شرط حکم برقرار است. حال فرض کنید گرافی با n راس و k یال داریم، و برای تمام گراف‌ها با مجموع راس و یال n + k - 1 و کم‌تر حکم برقرار است. حال v را راس با کم‌ترین درجه در نظر بگیرید.

• درجه‌ی v، صفر باشد - v را حذف می‌کنیم، بقیه‌ی گراف OK است، طبق فرض استقرا، حال v را اضافه می‌کنیم، باز هم ب‌م‌م همه ۱ می‌ماند.

• درجه‌ی v، یک باشد - ابتدا راس کنونی را v می‌گیریم، در هر گام اگر درجه‌ی راس کنونی از ۲ بیش‌تر بود، متوقف می‌شویم، وگرنه اگر دیگر راس دیگری نبود که بازدیدش نکرده بودیم، متوقف می‌شویم وگرنه به راس کنونی را برابر با راس همسایه‌ی راس کنونی که تا به حال بازدیدش نکردیم، قرارش می‌دهیم. از آن‌جایی که n متناهی‌ست جایی متوقف می‌شویم. مسیری به طول x با شروع از v داریم که هر راس میانی‌اش درجه‌ی دقیقاً ۲ دارد. به ترتیب به یال‌های مسیر با شروع از v، اعداد k و k- 1 و ... و k - x +1 می‌دهیم. هر راس که درجه‌اش ۲ است، در دو یال گذرنده از خود دو عدد پشت سر هم دارد، می‌دانیم که دو عدد q و q + 1 همواره نسبت به هم اولند. پس شرط مساله برای این رئوس برقرار است. حال تمام این مسیر را حذف می‌کنیم، گراف باقی‌مانده طبق فرض استقرا OK است. پس آن راس آخری که در آن متوقف شده بودیم، حتماً ب‌م‌م یال‌هایش ۱ است. با اضافه کردن مسیر حذف شده، ب‌م‌م آن راس باز هم ۱ می‌ماند و برای بقیه‌ی رئوس اضافه شده نیز درست است.

• درجه‌ی v، دو باشد - مانند قبل از هر دو سمت گراف را پیمایش می‌کنیم تا به دو راس u و w برسیم که درجه‌ی حداقل ۳ دارند. حال از مسیر u به w به هر یال به ترتیب k و k- 1 و ... می‌دهیم، هر راس دو عدد پشت سر هم را می‌گیرد، پس ب‌م‌م یال‌هایش ۱ است. حال این مسیر را حذف می‌کنیم (u و w حذف نمی‌شوند.) برای گراف باقی‌مانده صحیح است. حال رئوس حذف شده را اضافه می‌کنیم. u و w هم اکنون ب‌م‌م ۱ دارند (چرا که حداقل درجه‌ی ۲ داشته اند) و با اضافه شدن یال مسیر حذف شده تاثیری کذاشته نمی‌شود.

• درجه‌ی v، بیش از سه باشد - یعنی درجه هر کس بیش‌از ۳ است. یک یال را رویش k می‌نویسیم و حذفش می‌کنیم، درجه‌ی هر کس حداقل ۲ می‌ماند. طبق فرض استقرا گراف باقی‌مانده OK است، پس اگر یال حذف شده‌ی uv را باز گردانیم، از آن‌جایی که u و v هر دو درجه‌ی بیش‌تر از ۱ داشته‌اند در گراف باقی‌مانده، پس ب‌م‌م یال‌های هر دوشان ۱ است و با اضافه شده یال با شماره‌ی k باز هم ب‌م‌م 1 می‌ماند.

شکل برای حالت‌های ۲ و ۳ برای درک به‌تر:

برای همبند و نا همبند: اول طولانی ترین مسیر موجود رو انتخاب میکنم مثلا به طول m بعد از ۱ شرو ع میکنم وبه ترتیب یال های مسیر رو شماره گذاری میکنم بعد بدون در نظر گرفتن یال های شماره گذاری شده طولانی ترین مسیر رو تو گراف باقی مونده انتخاب میکنم بعد دوباره یال های این مسیر رو با باقی مونده اعداد شماره گذاری میکنم یعنی از عدد m+۱ به بعد وهمین طور ادامه میدم تا همه ی یال ها شماره گذاریشن حالا فرض کنین یه راس به اسم aباشه که ب م م اعداد روی یال های متصل به اون ۱ نباشه حالا یال p رو با کم ترین عدد در نظر بگیرین که به a متصله این راس تو یه طولانی ترین مسیر قرار داشته که شماره گذاری شده مطمئنن خودش تنها یی طولانی ترین مسیر نبوده چون یال هایی که از سمت a بهش وصلن بعد از اون شماره گذاری شدن همینطور هم حتمن این طولانی ترین مسیر شامل a میشده چون در غیر این صورت دیگه طولانی ترین مسیر نبوده ( یالهای متصل به a میتونستن ادامش باشن ) پس حتمن یه یال دیگه به a وصله که عددش با عدد روی a متوالیه پس حتمن ب م م اعداد روی این دو تا یال ۱ میشه در نتیجه ب م م اعداد روی یال های متصل به a حتما یک میشه که با فرض اول تناقض داره و اصلن راسی وجود نداره که ب م م یال های متصل بهش ۱ نشه!

خب من کامل نمی نویسم ولی تا حد ممکن توضیح میدم

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