به نام خدا

مجموعه ای با ماکسیمم تعداد اعضا را که بتوان آن ها را رنگ زد به طوری که از هر مجموعه ی 3 عضوی حداکثر 2 عضو آن رنگ شده باشد(از هیچ مجموعه ای هر 3 عضو رنگ نشده باشند) $T$ می نامیم.

فرض خلف می کنیم که $|T| \lt [\frac{n}{3}]$. در این صورت $n-|T| \gt 2.[\frac{n}{3}]$. می دانیم که هر کدام از اعضای $X-T$ اگر به T اضافه شوند، یکی از مجموعه های 3 عضوی درون T پیدا خواهد شد. پس با اضافه کردن هر کدام از اعضای $X-T$ به $T$ وسپس حذف آن، حداقل یکی از مجموعه های 3 عضوی در T ظاهر و سپس حذف می شود. به بیان دیگر به ازای هر کدام از اعضای مجموعه $X-T$ مانند $i$، یک سه تایی پایدار وجود دارد که شامل $i$ و دو عضو از $T$ است.

بنابراین در بین اعضای $X-T$ حداکثر تعداد سه تایی های پایدار برابر $f \lt [\frac{n}{3}]$ است.

یک مجموعه مانند $A$ با $[\frac{n}{3}]$ عضو از $X-T$ انتخاب می کنیم. براساس فرض خلف، در این مجموعه باید 3 عضو باشند که تشکیل یک سه تایی پایدار بدهند. عمل زیر را $[\frac{n}{3}]$ بار تکرار می کنیم:

یکی از اعضای یکی از این سه تایی ها را از $A$ حذف می کنیم و به حای آن عضو دیگری از $X-T$ که تا به حال در $A$ حضور نداشته است را به $A$ اضافه می کنیم.

در هر بار اجرا اگر هیچ سه تایی پایداری در $A$ یافت نشد، فرض خلف باطل است و حکم مسئله ثابت می شود.

می دانیم که $|X-T| \gt 2.[\frac{n}{3}]$. پس در هر بار اجرای عمل بالا حتمن عضوی از $X-T$ وجود دارد که تا آن لحظه درون $A$ نبوده است. در انتها مجموعهی $A$ شامل $[\frac{n}{3}]$ است و با توجه به اینکه ما هر بار یک سه تایی پایدار را از $A$ حذف کرده ایم و همچنین تعداد کل سه تایی های پایدار در $X-T$ از $[\frac{n}{3}]$ کمتر است پس در $A$ هیچ سه تایی پایداری وجود ندارد.

از آنجایی که $|A|=[\frac{n}{3}] \gt |T|$ پس فرض خلف باطل است و مجموعه ای مانند $T$ با حداقل $[\frac{n}{3}]$ عضو وجود دارد که هیچ سه تایی پایداری درون آن نیست و می توان اعضای آن را رنگ کرد به طوری که از هر سه تایی پایدار حداکثر 2 عضو رنگ شود.