آیا «گراف $G$ ناهمیلتونی است هرگاه $G$ گرافی دو بخشی باشد به طوری که دو بخش آن با هم، هم اندازه نباشند»؟

Question

ثابت کنید که گراف $G$ ناهمیلتونی است هرگاه $G$ گرافی دو بخشی باشد به طوری که دو بخش آن با هم، هم اندازه نباشند. یعنی $ \mid x \mid \neq \mid y \mid $.

تلاش خودم: اگر تعداد راس‌های گراف فرد باشد گراف دور فرد دارد که با دوبخشی بودن آن در تناقض است.

Comments

تلاش خودم:
اگر تعداد راس های گراف فرد باشد گراف دور فرد دارد که با دو بخشی بودن آن در تناقض است.

---

@Math_green تلاش خودتان را در ادامهٔ همان متن پرسش بنویسید مانند ویرایشی که برایتان کردم.

Answer 1

احتمالا متن پرسش‌تان را اشتباه نوشته‌اید. اگر فرض کنیم که منظرو متن‌تان است که «یک گراف ناهمیلتونی است اگر و تنها اگر گرافی دوبخشی با تعداد نابرابری گره در دو بخشش باشد» که اصلا همیلتونی بودن و نبودن الزامی به دوبخشی بودن ندارد.

1. دوبخشی که همیلتونی باشد:

2. دوبخشی که همیلتونی نباشد:

3. نادوبخشی که همیلتونی باشد:

4. نادوبخشی که همیلتونی نباشد:

پس اصلا گزاره‌ای اگر و تنها اگر برای همیلتونی (یا ناهمیلتونی) با شرط دوبخشی نمی‌توانید بسازید (چه تعداد گره‌ها در دو بخش یکی باشد چه نباشد).

اکنون اگر منظورتان فقط گزارهٔ یک‌طرفه و آن هم در سمت برعکس چیزی که نوشتید باشد، یعنی «یک گراف دوبخشی با تعداد نابرابر گره در دو بخشش حتما ناهمیلتونی است» که در این صورت نمونهٔ شمارهٔ ۱ در بالا برایتان مثال نقض است. برایتان هم باید (از قسمت نخست پاسخ) روشن باشد که چرا اصلا به سراغ سمت دیگر گزاره به شکل یک طرفه نرفتم.