قسمت اول

گراف روابط دوستی دانش‌آموزان را در نظر می‌گیریم. در واقع مسئله از ما خواسته است تا اثبات کنیم گرافی $nk$ راسی با$\binom{k}{2}n^2$ یال وجود دارد که افراز آن به خوشه‌های $k$ راسی یکتا مشخص شود. برای اثبات این حکم از استقرا روی $n$ استفاده می کنیم.

پایه: حکم برای $n=1$ برقرار است چرا که $\binom{k}{2}$ یال دقیقا یک خوشه را تشکیل می‌دهند.

فرض می‌کنیم برای کلاسی با $nk$دانش‌آموز چنین حالتی وجود داشته باشد.

کلاسی با $(n+۱)k$ نفر را در نظر بگیرید.ابتدا $k$ نفر از کلاس حذف و برای $nk$ نفر باقی‌مانده تعداد $\binom{k}{2} n^2$ رابطه‌ی دوستی در نظر می‌گیریم. حال $k$ نفر را به $nk$ نفر برمی‌گردانیم. برای این که شرایط مساله بر قرار باشد لازم است $\binom{k}{2} n^2((n+1)^2-n^2 ) = \binom{k}{2} n^2(۲n+۱)=\binom{k}{2} n^2+(k-۱)\times (nk)$ رابطه‌ی دوستی به روابط دوستی اضافه کنیم.به $\binom{k}{2}$ رابطه دوستی که برای گروه کردن $k$ دانش‌آموز نیاز داریم. پس$(k-۱)\times (nk)$ رابطه‌ی دوستی باقی می‌ماند که آن‌ها را باید به شکلی نسبت دهیم. با کمی دقت در میابیم که کافی است از شکل همین عبارت این ایده به ذهن می‌رسد که از آن $k$ نفر، یک نفر را کنار گذاشته‌ایم و بقیه را با تمام $nk$ نفر دوست کرده‌ایم. حال ادعا می‌کنیم که با این ساختار گروه بندی یکتا است (چرا؟).

قسمت دوم

طبق آنچه در صورت سوال آمده، تعداد روابط دوستی حداقل $\binom{k}{2} n^2+1$می‌باشد و حداقل یک گروه‌بندی وجود دارد. روابط دوستی غیر از رابطه‌ی هم گروه‌ها در این گروه‌بندی را در نظر بگیرید. تعداد این رابطه‌ها حداقل برابر است با$\binom{k}{2} n^2+1 – n\binom{k}{2} = \binom{k}{2} n(n-1)+1$ .

اما تعداد زوج‌ گروه‌ها برابر با $\binom{n}{2}$ است و $\binom{k}{2}n(n-1)+1$ رابطه دوستی بین این $\binom{n}{2}$ زوج گروه قرار دارد. پس طبق اصل لانه‌کبوتر حداقل یک زوج گروه وجود دارد که تعداد روابط دوستی بین اعضای آن بیش‌تر از یا مساوی با $⌈\frac{(\binom{k}{2} n(n-1)+1 )}{(\binom{n}{2} )}⌉ = k\times(k-1)+1$ باشد. از سوی دیگر کل روابط دوستی بین اعضای این دو گروه با یکدیگر حداکثر $k\times k$ تا بوده و حالا تنها $k-1$ رابطه‌ی دوستی از کل این رابطه‌ها را نداریم. پس در هر گروه عضوی هست که با تمامی اعضای گروه دیگر دوست باشد و در نتیجه با عوض کردن جای این دو نفر می‌توان یک گروه بندی جدید ایجاد کرد. با توجه به آنچه گفته شد در صورتی‌که تعداد یال‌ها بیش‌تر از $\binom{k}{2} n^2$ باشد و حداقل یک گروه‌بندی وجود داشته باشد، نمی‌توان گروه‌بندی را به صورت یکتا مشخص کرد.