افراد را رأسهای یک گراف و رابطه دوستی را یال نشان دهید.فرض کنید در جه رأسها به صورت زیر باشد:
$d_1 \leq d_2 \leq ... \leq d_n$
می دانیم که در یک گراف ساده ( بدون طوقه و هر دو رآس حداکثر با یک یال وصلند ) مجموح یالها حداکثر $ \binom{n}{2} $ است.حالا اگر هیچ دو نفری تعداد دوستان یکسانی نداشته باشند پس:
$0 \leq d_1<d_2<...<d_n \Rightarrow d_1+d_2+...+d_n \geq 1+2+...+(n-1)= \frac{(n-1)n}{2} $
بنابر این باید مجموع رأسها مساوی $ \frac{n(n-1)}{2} $ باشد یعنی گراف کامل است یعنی درجۀ هر رآس $ \frac{n-1}{2} $ است و چون ($n \geq 2$) پس حداقل دو نفر هستند که تعداد دوستانشان برابر و مساوی $ \frac{n-1}{2} $ است که تناقض است.
$ \Box $
