جواب فعالیت صفحه ۴۰ ریاضیات گسسته

این سؤال را مانند نمونهٔ «اثبات» و گام‌های کتاب حل می‌کنیم: در هر گام، با توجه به درجهٔ رأس، وجود یک همسایهٔ مناسب را توضیح می‌دهیم.

گام ۱: رأس \(v_1\) را در نظر می‌گیریم. چون \(\delta(G) \geq 4\)، یعنی کوچک‌ترین درجهٔ گراف حداقل ۴ است، پس درجهٔ هر رأس از جمله \(v_1\) حداقل ۴ است. بنابراین \(v_1\) حداقل به ۴ رأس متصل است و حتماً به رأسی دیگر وصل است. آن رأس را \(v_2\) می‌نامیم.

گام ۲: رأس \(v_2\) درجه‌اش حداقل ۴ است، پس حداقل به ۴ رأس متصل است. یک رأس از این ۴ رأس ممکن است \(v_1\) باشد، ولی بقیه‌اش (حداقل ۳ رأس) با \(v_1\) فرق دارند. پس \(v_2\) حتماً به رأسی به جز \(v_1\) متصل است. آن رأس را \(v_3\) می‌نامیم.

گام ۳: رأس \(v_3\) درجه‌اش حداقل ۴ است و حداقل به ۴ رأس متصل است. این رأس‌ها ممکن است \(v_1\) و \(v_2\) باشند، اما حداقل ۲ رأس دیگر وجود دارد که در مجموعهٔ \(V(G)-\{v_1,v_2\}\) هستند. پس \(v_3\) حتماً به رأسی از این مجموعه وصل است. آن رأس را \(v_4\) می‌نامیم.

گام ۴: رأس \(v_4\) درجه‌اش حداقل ۴ است و حداقل به ۴ رأس متصل است. این رأس‌ها ممکن است \(v_1\)، \(v_2\) و \(v_3\) باشند، اما حداقل یک رأس دیگر وجود دارد که در مجموعهٔ \(V(G)-\{v_1,v_2,v_3\}\) است. پس \(v_4\) حتماً به رأسی از این مجموعه وصل است. آن رأس را \(v_5\) می‌نامیم.

گام ۵: رأس‌های \(v_1, v_2, v_3, v_4, v_5\) دو به دو متمایزند و هر رأس با رأس بعدی در گراف مجاور است. بنابراین مسیر
\[v_1v_2v_3v_4v_5\]
یک مسیر در گراف \(G\) است که طول آن برابر با تعداد یال‌های آن، یعنی ۴ است.

نتیجه: گراف \(G\) شامل یک مسیر به طول ۴ است، و چون ۴ بزرگ‌تر یا مساوی ۴ است، گراف \(G\) شامل یک مسیر به طول بزرگ‌تر یا مساوی ۴ است.