فرض کنید گراف دارای $n$ راس می‌باشد،ابتدا ثابت می‌کنیم برای هر $n$ می‌توانیم اعداد یک تا $n$ را به رئوس گراف طوری نسبت دهیم که هر یال از راسی با عدد متناظر کم‌تر به راسی با عدد متناظر بیش‌تر متصل باشد: با استقرا روی $n$ حکم را ثابت می‌کنیم: برای $n=1$ که حکم واضح است ، حال فرض کنید حکم برای $n$ برقرار باشد حکم را برای $n+1$ ثابت می‌کنیم:

با شروع از یک راس و رفتن از آن به یکی از رئوسی که به این راس مورد نظر یال دارند و ادامه این حرکت با توجه به اینکه گراف فاقد دور است به راس تکراری نمی‌رسیم و با توجه به اینکه گراف متناهی راس دارد باید به راسی برسیم که هیج یال ورودی ندارد،حال به این راس عدد 1 را نسبت می‌دهیم و با استفاده از فرض استقرا به بقیه رئوس می‌توان اعداد 2 تا $n-2$ را به گونه ای نسبت داد که حکم مسئله برقرار باشد.

حال داریم اگر به جای رئوس اعداد متانظرشان را در ترتیب ذکر شده قرار دهیم،با هر حرکت تعداد نا به جایی ها (دوتایی هایی که عدد کوچک‌تر در ترتیب مورد نظر پس از عدد بزرگ‌تر آمده است) دقیقا یک واحد کم میشود،دلیل این امر این است که در هر مرحله با تعویض مکان دو عدد مانند $a$ و $b$ هر دوتایی که هر دو زوج آن مخالف $a$ یا $b$ هستند که هیچ تغییر وضعیتی نمیدهد و به طبع آن تغییری در تعداد نابه‌جایی‌ها نمی‌دهد،ضمنا هر دوتایی که دقیقا یکی از دو زوج آن برابر $a$ یا $b$ است با دو تایی که عضو غیر $a$ و $b$ آن با عضو دیگر $a$ و $b$ میسازند با هم در مجموع تغییری در تعداد نابه‌جایی هاایجاد نمی‌کنند و دو تایی $a$ و $b$ هم دقیقا یک تغییر ایجاد می‌کنند.

حال داریم تعداد نابه جایی ها متناهی است زیرا تعداد رئوس گراف متناهی است بنابراین بعد از متناهی حرکت دیگر نمی‌توان حرکتی انجام داد زیرا در هر حرکت تعداد نابه‌جایی‌ها دقیقا یک واحد کاهش می‌یابد.