بر روی n - k استقرای ضعیف میزنیم!

بعنوان پایه اگر n = k باشه چون در هر کلاس دقیقن یک نفر است و بین هر دو کلاسی حداقل یک رابطه ی دوستی هست، پس همه با هم دوستند و میتوان در یک گروه همه رو گذاشت.

حال فرض کنیم n > k
کلاسی را در نظر میگیریم که بیشترین تعداد دانش آموز را دارد. این تعداد بزرگتر از 1 است (چون n > k... لانه کبوتری!) . حال ما دو نفر از این کلاس رو میگیریم و فرض میکنیم یک نفرند (روابط دوستی هم میمونند ... یعنی این نفر ما (مینامیمش A) اگر با کسی دوست است که حداقل یکی از اون دو نفر قبلیه باش دوست بوده باشند.)
طبق فرض استقرا میتوانیم دانش آموزان را در n – k دسته تقسیم کنیم (n یدونه کوچیک میشه). اکنون میخایم مسئله رو برای n حل کنیم دسته ای رو در نظر میگیریم که A رو شامل میشه. بجز A هر کسی اینجاست یا با نفر اول A دوست بوده یا با نفر دوم و یا هردو. دسته ای جدید میسازیم که شامل نفر اول A و تمام کسانی از اون دسته است که با نفر اول A دوست هستند. میدانیم که تمام کسانی که در اون دسته بودند با هم دوستند و از آنجا که همشون با نفر اول A هم دوستند، پس در این دسته ی جدید هم همه باهم دوستند!
حال در دسته ی قبلی بجای A ، نفر دوم A رو میگذاریم. ازآنجایی که تمامی کسانی که با نفر اول A دوست بودند از این دسته رفته اند پس حتمن هرکسی اینجا مونده با نفر دوم A دوسته و از قبل هم که خودشون با هم دوست بودند پس در این دسته هم حکم مسئله صدق میکنه.

پس گام استقرا نیز ثابت شد!$^_^$

از استقرای قوی روی $n$ استفاده میکنیم.

پایه استقرا:‌ برای $n=1$ چون $k=1$ میتوان یک دانش آموز را در $n-k+1=1$ دسته قرار داد.

فرض استقرا:‌برای همه اعداد $m$ و $k$ کوچکتر از $n$ ثابت کرده باشیم اگر $m$ دانش آموز را به $k$ کلاس تقسیم کنیم که بین هر دو کلاس یک جفت دانش آموز آشنا باشد، آنگاه کل دانش آموزان را میتوان به $m-k+1$ خوشه افراز کرد که در هر خوشه همه جفت دانش آموزان آشنا باشند.

حکم استقرا: برای آن که حکم را در مورد $n$ دانش آموز که در $k$ کلاس تقسیم شده اند اثبات کنیم، یک کلاس از دانش آموزان را در نظر میگیریم و فرض می کنیم این کلاس $a$ دانش آموز دارد. این کلاس را موقتا حذف می کنیم. $k-1$ کلاس باقیمانده جمعا $n-a$ دانش آموز دارد و بین هر دو کلاس باقیمانده هم یک جفت آشنا وجود دارد. پس طبق فرض استقرا میتوان دانش آموزان باقیمانده را به $(n-a)-(k-1)+1=n-a-k+2$ خوشه افراز کرد.

حال کلاس آخر را بر میگردانیم. به تمام دانش آموزانی از $k-1$ کلاس دیگر که با حداقل یکی از دانش آموزان کلاس آخر آشنا هستند یک سیب میدهیم. چون کلاس آخر با هر یک از $k-1$ کلاس دیگر یک جفت دانش آموز آشنا دارد، پس حداقل $k-1$ دانش آموز سیب دارند. پس دانش آموزانی که سیب ندارند حداکثر $(n-a)-(k-1)$ نفر هستند و چون این عدد یک واحد کمتر از تعداد خوشه هاست، طبق اصل لانه کبوتری میدانیم خوشه ای وجود دارد که هیچ دانش آموز بی سیبی در آن نیست، یعنی همه اعضای آن خوشه سیب دارند (که به آن خوشه سیب میگوییم). یعنی همه اعضای خوشه سیب، آشنایانی در بین کلاس آخر دارند.

به ازای هر فرد از کلاس آخر یک خوشه جدید میسازیم و همه دانش آموزان خوشه سیب را به دلخواه در بین خوشه های جدید تقسیم میکنیم طوری که هر دانش آموز سیب دار در خوشه یکی از آشنایان خود از کلاس آخر قرار بگیرد. چون دو به دوی اعضای خوشه سیب با هم آشنا بوده اند، پس در هر خوشه جدید همه دانش آموزان آشنا هستند. از خوشه های قبل یک واحد کم شد و در عوض $a$ خوشه جدید به وجود آمد. پس در کل $(n-a-k+2)+a-1=n-k+1$ خوشه خواهیم داشت.