گراف

[Devaince]

ثابت کنید اگر گرافی غیر دو بخشی و بدون مثلث باشد: 5/(S<(2*n
(منظور از s دلتای کوچک است. )

 

[erfan_ashorian]

پاسخ : گراف

راهنمایی‌ » ابتدا به برهان خلف فرض کنید s>= 2n/5 باشد! سپس کوچکترین دور فرد را در نظر بگیرید(همچین دوری حتما داریم چون گراف غیر دوبخشیست) بدیهیست که توی این دور یال نداریم یعنی یالی نداریم که بین دو راس از این دور باشد چون در این صورت دور فرد کوچکتری بوجود می آید حال ثابت کنید راسی وجود دارد که به سه راس از این کوچکترین دور متصل است و . . . .