قبل از هر چیز من صورت سوال را تصحیح کردم و کلمۀ ساده را به گراف اضافه کردم.حکم برای گرافهای غیر ساده صحیح نیست.(چرا؟)
توجه داریم که مسیری به طول $n$ دنباله ای مانند $e_1u_1e_2u_2...e_nu_ne_{n+1}$ به ترتیب از راس ها و یالهای گراف است که راسها و یالها تکراری نیستند مگر راسهای ابتدا و انتها که در این حالت مسیر را دوری به طول $n$ مینامند.(اگر گراف ساده باشد، در دنبالۀ فوق می توان یالها را ننوشت).(چرا؟)
حالا با استقرا روی $k$ اثبات را انجام می دهیم:
اگر $k=1$ یا $k=2$ (برای اطمینان ) اثبات ساده است.(بدیهی نیست.به قول یکی از ریاضیدانان ، در ریاضیات هیچ چیز بدیهی وجود ندارد.)
حالا فرض کنید که حکم برای $k$ درست باشد.(فرض استقراء).حالا گرافی ساده مانند $G$ را در نظر بگیرید که:
$ \delta (G) \geq k+1 $
$ \Rightarrow \delta (G) \geq k$
پس بنابه فرض استقرا $G$ دارای یک مسیر بطول $k$ مانند $e_1u_1e_2u_2...e_ku_ke_{k+1}$ است.حالا توجه کنید که چون درجۀ راس $e_{n+1}$ حداقل $k+1$ است پس به راسی دیگر مانند $e$ که از تمامی $e_i$ ها متمایز است به وسیلۀ یالی مانند $u$ وصل است.لذا طبق تعریف $e_1u_1e_2u_2...e_nu_ne_{n+1}ue$ مسیری در $G$ است که طول آن $k+1$ است.
$ \Box $
