شاه کلید نکات
شاه کلید سوال
فرض کنید G یک گراف باشد و داشته باشیم \(δ(G) ≥ 4 \) می خواهیم نشان دهیم که G شامل یک مسیر به طول بزرگتر یا مساوی 4 است.
1 رأس دلخواه v1 را در G در نظر می گیریم. حتما v1 به رأس دیگری متصل است. (چرا؟) فرض کنیم آن رأس v2 باشد.
زیرا اگر به رأس دیگری متصل نباشد، درجه آن صفر خواهد بود. در حالی که طبق مسئله کمترین درجه 4 در نظر گرفته شده است.
2 حتما v2 به رأسی به جز رأس v1 متصل است. (چرا؟) فرض می کنیم آن رأس v3 باشد.
زیرا اگر چنین نباشد، درجه آن 1 خواهد بود که با فرض مسئله (کمتریم درجه 4 است) تناقض دارد.
3 حتما v3 به رأسی از مجموعه V(G) = {v1 , v2} وصل است (چرا؟) فرض می کنیم آن رأس v4 باشد.
زیرا در غیر این صورت، درجه آن حداکثر 2 خواهد بود و با فرض مسئله (کمترین درجه 4 است) تناقض دارد.
4 حتما v4 به رأسی از مجموعه V(G) = {v1 , v2 , v3} وصل است (چرا؟) فرض می کنیم آن رأس v5 باشد.
زیرا اگر چنین نباشد، درجه آن حداکثر 3 شده که با فرض مسئله (کمترین درجه 4 است) تناقض دارد.
5 مسیر \({v_1}{v_2}{v_3}{v_4}{v_5}\) یک مسیر به طول 4 در گراف G است.
1736019749.png)
