قضیه گراف دوبخشی است اگر و فقط اگر شامل دور فرد نباشد

Question

در قضیه اینکه یک گراف دوبخشی است اگر و فقط اگر هیچ دور فردی نداشته باشد برای قسمت دوم که می‌خواهیم ثابت کنیم G یک گراف دوبخشی است میگوییم فرض میکنیم G همبند است . سوال ؟ چرا فرض میکنیم G. همبند است

از کتاب نظریه گراف باندی مورتی

Answer 1

با سلام؛

دو حالت داریم یا گراف ناهمبند است یا همبند.

اگر ناهمبند باشد واضح است که شامل یک دور نیست و در نتیجه دوری به طول فرد ندارد.

اگر همبند باشد، مطابق آنچه که در کتاب باندی مورتی یا کتاب داگلاس بی وست گفته شده اثبات را انجام خواهید داد.

در واقع کتاب برای اینکه اثبات طولانی نشود، فرض کرده که خواننده حالت ناهمبند بودن برایش بدیهی و واضح است.