فرض کنید G یک گراف باشد و δ(G) بزرگتر یا مساوی k، ثابت کنید این گراف حداقل دارای یک مسیر به طول k است.

Question

فرض کنید G یک گراف ساده باشد و $\delta (G) \geq k$ (درجۀ هر راس حداقل $k$ است)، ثابت کنید این گراف حداقل دارای یک مسیر به طول $k$ است.

Answer 1

قبل از هر چیز من صورت سوال را تصحیح کردم و کلمۀ ساده را به گراف اضافه کردم.حکم برای گرافهای غیر ساده صحیح نیست.(چرا؟)

توجه داریم که مسیری به طول $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$