فرض کنید که q > {p-1 \choose{2} } از برهان خلف حکم را ثابت میکنیم فرض کنید گراف نا همبند باشد و G_{1} , G_{2} ,.., G_{r} مولفه های همبندی باشند پس V(G)=V( G_{1})+V(G_{2})+...+V(G_{r})
زمانی گراف دارای بیشترین یال است که تک تک مولفه های همبندی یک گراف کامل باشندو در این حالت تعداد یالهابرابر می شود با
{V( G_{1}) \choose{2} } +{V( G_{2}) \choose{2} }+...+{V( G_{r}) \choose{2} } و به راحتی با استقرا می توان نشان داد که {V( G_{1}) \choose{2} } +{V( G_{2}) \choose{2} }+...+{V( G_{r}) \choose{2} } < {V( G) \choose{2} }و این تناقض است با فرض مساله
با استقرا حکم را ثابت می کنیم یعنی نشان میدهیم اگر گرافی همبند باشد آنگاه q \geq p-1
پایه استقرا:
فرض کنیم که گرافی همبند با دو راس باشد چون گراف همبند است لذا بین این دو راس یک یال داریم.
حال فرض کنید که حکم برای هر گراف همبند با k راس درست باشد نشان میدهیم حکم برای هر گراف همبند با
k+1 راس نیز برقرار است
فرض کنید گراف همبند k+1 راس داشته باشد اگر زیر گراف با k راس دلخواه را در نظر بگیریم طبق فرض استقرا تعداد یالها بزرگتر مساوی با k-1 است و راس k+1 ام را همراه زیر گراف در نظر میگیریم اگر یالی بین این دو وجود نداشته باشد گراف اولیه ناهمبند خواهد شد اما طبق فرض همبند است لذا حداقل راس k+1 ام با یک راس از زیر گراف یالی تشکیل میدهد پس تعدادیال ها ی گراف حداقل k است و این حکم را ثابت میکند.
نشان میدهیم که اگر q=p-1 آنگاه گراف دارای دور نیست. از برهان خلف کمک میگیریم فرض کنید دارای دور باشد آنگاه بین دو راس دو مسیر متفاوت داریم که اگر یکی از یالهای یکی از مسیرها را حذف کنیم گراف باز همبند خواهد ماند و در گراف حاصل داریم
q=p-2 < p-1 اما طبق قسمت قبل گرافی با این خاصیت ناهمبند است و این تناقض است.
برای قسمت آخر چون گراف همبند است اگر دور نداشته باشد آنگاه گراف یک درخت خواهد شد و در درخت داریم q=p-1 اما چون در اینجا q=p لذا باید دور داشته باشد پس بین دو راس دو مسیر متفاوت داریم اگر یکی از یالها را حذف کنیم(از یکی از مسیرها) آنگاه q=p-1 پس طبق قسمت قبل دوری دیگر نداریم.
