فرض میکنیم گرافی 3 بخشی داریم که هر بخش $n$ راس داره و بیشتر از $2n^2$ یال تو گراف هست. ثابت میکنیم که گرافمون حداقل $n$ مثلث داره!
روی $n$ استقرا میزنیم. برای $n=1$ که گرافمون یک مثلثه، حله!
حال $n > 1$.

لم) گرافمون حداقل یه مثلث داره!
$3n^2$ تا یال گراف رو به $n^2$ تا مثلث افراز میکنیم: رئوس هر بخش رو از 0 تا $n-1$ شماره گذاری میکنیم. یال بین راس $a$ از بخش اول و راس $b$ از بخش دوم، با دو یال به راس $(a+b) mod\ n$ در بخش سوم هم دسته اند. الان هر یالی رو بگیریم دسته ای که توشه رو میشه یکتا مشخص کرد، پس یالامون افراز شدن! خب حالا گرافمون بیشتر از $2n^2$ تا یال داره و یالاش رو توی $n^2$ تا مثلث جا دادیم، پس طبق اصل لانه کبوتری یکی از این $n^2$ تا دسته هست که توش 3 تا یال باشه و اون دسته یه مثلثه!

یک مثلث تو گراف در نظر میگیریم! راساش باید در دسته های مختلف باشن. اگه با حذف کردن این 3 راس بیشتر از $2(n-1)^2$ تا یال تو گراف باقی بمونه، طبق فرض استقرا $n-1$ تا مثلث دیگه پیدا میشه و مسئله حله. فرض میکنیم حداکثر $2(n-1)^2$ یال هست که هیچ سریشون تو مثلث پیدا شده نیست. یعنی حداقل $4n-4$ یال داریم که از راسی داخل مثلث به $3n-3$ راس خارج از مثلث وصل شدن. اول اون یال ها رو از گراف حذف میکنیم و به ترتیب دلخواه شروع میکنیم اون یال ها رو اضافه کردن. هر یالی که اضافه بشه اگه اون راسیش که داخل مثلث نیست برای اولین بار از این یالا بش اضافه شده باشه، یاله برامون اهمیت نداره. حداکثر $3n-3$ یال بی اهمیت وجود دارند (هر راس خارج از مثلث حداکثر یک یال!). اگه یالی بی اهمیت نباشه یعنی یال دیگه ای از مثلث به این راس هست و این دو یال + یک یال از مثلث تشکیل یک مثلث جدید میدن! پس حداقل $n-1$ مثلث هم اینطور پیدا میشه و سرجمع میشه $n$ تا!

سلام خب منم یه ایده دوگونه شماری میدم که تکمیل شه .

بیاید یه گراف دو بخشی بسازید که رئوس بالای اون متناظر با سه تایی ها از شهر ها (از سه کشور متفاوت) و رئوس پایین آن متناظر با یال های گراف اصلی می کنیم . حالا بین دو تا راس e و سه تایی $ (u,v,n) $یال میگزاریم اگر وتنها اگر اون یال دو تا از راس های اون سه تایی رو بهم متصل کنه . حالا دوگونه شماری میزنیم رو تعداد یال ها (در این گراف جدید ) هر راس از پایین به دقیقا 10 تا راس از بالا متصل است . حالا پس در مجموع (E تعداد یال ها در گراف جدید ) $E > 200×10 = 2000$ پس طبق لانه کبوتری $\exists u \rightarrow d(u)>\frac{2000}{1000}=2 $ .

حالا برای بخش دوم نیز یه محاسبه ریاضی داره : چون در جه هر راس از پایین 10 است پس تعداد یال ها در انتها نیز مضربی از 10 میباشد . پس با یه حالت بندی ساده روی تعداد رنوس درجه سه بالا میتونیم به این برسیم باید حداقل 10 تا درجه سه داشته باشیم .(یعنی 10 تا مثلث)