گراف دو بخشی¶

ارتباط با دور فرد¶

یک گراف دوبخشی است اگر و تنها اگر دور فرد نداشته باشد. یک طرف این قضیه واضح است چون اگر یک گراف دور فرد داشته باشد، آن گاه در هر افراز به دو دسته، یک دسته بیش از نیمی از رئوس این دور را خواهد داشت و در نتیجه درون آن دسته یال پیدا می شود و یعنی گراف دو بخشی نیست.

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

در ادامه فرض می کنیم که گراف همبند است، زیرا اگر همبند نباشد، می توان حکم را برای مولفه های آن ثابت کرد و نتیجه گرفت که هر مولفه دو بخشی است و سپس بخش اول هر مولفه را به عنوان بخش یک و بخش دوم را به عنوان بخش دو معرفی می کنیم.

یک راس دلخواه را در نظر بگیرید. چون گراف همبند است، این راس یا به هر کسی مسیر فرد یالی دارد و یا مسیر زوج یالی. رئوس با مسیر فرد را درون دسته یک و رئوس با مسیر زوج را درون دسته دو قرار می دهیم. برای این که نشان دهیم گراف با این دسته ها دو بخشی است، برهان خلف می زنیم و فرض می کنیم که درون یک دسته یال وجود داشته باشد. در آن صورت هم مسیر فرد از راس اولیه به راس ها وجود خواهد داشت و هم مسیر زوج، که تناقض است.

وجود زیرگراف دوبخشی با نیمی از یال ها¶

هر گراف \(m\) یالی، زیر گرافی دارد که بیش از \(\frac{m}{2}\) یال دارد. برای اثبات، بزرگ ترین زیر گراف فراگیر دو بخشی را در نظر بگیرید. یک راس را در نظر بگیرید که بیش از نیمی از یال هایش در سمت خودش باشند. اگر چنین راسی وجود نداشته باشد جمع درجات رئوس در زیر گراف بیش تر مساوی نصف جمع در حالت عادی یعنی بیشتری مساوی m است که از این مطلب حکم نتیجه می شود.

اما اگر چنین راسی وجود داشته باشد، آن راس را به بخش دیگر می بریم و یال های سمت خودش که بیش از نصف درجه اش و در نتیجه بیش از حالت قبل است، که با فرض اکسترمال در تناقض است.