منقبض کردن¶

مثال¶

برای مثالی با این میزان یال، می توانید یک راس را در وسط گراف بگذارید و به ازای هر دو راس، یک مثلث که شامل این راس هست نیز بسازید.

اثبات بیشینه بودن¶

در این جا با استقرا ثابت می کنیم که در هر گرافی که دور هایش اشتراک یالی ندارند، \(2m \le 3n-1\) برقرار است. کوچک ترین مثال نقض این قضیه را در نظر بگیرید. این گراف نمی تواند بدون دور باشد چون در این صورت تعداد یال هایش از راس هایش کمتر است و یعنی حکم برایش برقرار است. واضح است که دور های این گراف نمی توانند وتر داشته باشند. (یعنی یالی درون آن ها وجود داشته باشد) چون در این صورت دو دور با اشتراک یالی به وجود می آید. و هم چنین یک راس نمی تواند به دو راس از یک دور یال داشته باشد. پس یکی از دور های این گراف را منقبض می کنیم. گراف همچنان ساده می ماند و می توان نشان داد که دور هایش همچنان اشتراک یالی ندارند. (این مطلب را ثابت کنید تا روی انقباض شهود بگیرید. ) و چون کوچک ترین مثال نقض را در نظر گرفته بودیم، در گراف جدید حکم برقرار است. اگر دوری به طول k را منقبض کرده باشیم، k یال و \(k-1\) راس از گراف حذف می شوند. پس داریم:

و از قبل می دانستیم که:

از این دو گزاره در می یابیم که:

که یعنی دوری که حذف کردیم کم تر از ۳ راس داشته که در گراف های ساده ممکن نیست. از این مطلب به تناقض می رسیم. با کمی دقت می توان دریافت که برابری تنها زمانی رخ می دهد که k دقیقا برابر 3 باشد و این یعنی تمام دور های گراف مثلث باشند. (همانگونه که مثال ما این شرط را داشت)