به نام خدا

پایه استقرا: به ازای $n=1$ یک گراف 3 رأسی کامل خواهیم داشت که یک یال از آن انتخاب می کنیم.

فرض کنید حکم به ازای $n=k$ درست باشد. یک گراف $2k+3$ رأسی کامل ;که یال های آن با 3 را رنگ $A,B,C$ رنگ شده اند مانند $G$ در نظر بگیرید. ثابت می کنیم می توان $k+2$ رأس و یک رنگ را طوری انتخاب کرد که از هر کدام از آن ها مسیری تک رنگ و از رنگ انتخابی به هر رأس دیگر از این $k+2$ رأس وجود داشته باشد.

فرض کنید $T$ بزرگترین مجمموعه ای از رئوس باشد که هردوتایی از آن ها با یک مسیر تک رنگ و از یک رنگ مشخص مانند $X$ باشد.

فرض می کنیم که $n(T) \lt k+2$. در اینصورت با توحه به فرض استقرا $n(T)=k+1$. بدون تغییر در شرایط مسئله فرض کنید $X=A$. دو رأس عضو $T$ را زا گراف حذف می کنیم. بنابر فرض استقرا یک مجموعه $n+1$ رأسی مانند $T'$ وجود دارد که از هر رأس آن به هر رأس دیگر مسیری تک رنگ و از رنگی مانند $X'$ وجود دارد. دو رأس حذف شده را به گراف بازمی گردانیم.

اگر $X=X'$ :

آنگاه واضح است که $T \cap T'=\varnothing$. همچنین با توجه به اینکه $n(G)=2k+3$. پس رأسی مانند $u$ وجود دارد که عضو هیچ کدام از دو مجموعه نیست و یال های بین آن و رئوس دو مجموعه از دو رنگ $B$ و $C$ هستند. چون $2k+2$ یال بین $u$ و رئوس دیگر وجود دارد. بنابر اصل لانه کبوتری $k+1$ یال از این یال ها از یک رنگ مانند $B$ هستند و مجموعه رئوسی که با این رنگ به $u$ متصل شده اند و خود $u$ تشکیل یک مجموعه $k+2$ رأسی را می دهند که هر دوتایی از آن ها با یک مسیر تک رنگ $B$ به هم مسیر دارند. بنابرایین $n(T) \ge k+2$ و این خلاف فرض است. پس فرض خلف باطل است و $n(T) \ge k+2$.

اگر $X \neq X'$ :

فرض کنید $X'=B$.

همچنبن فرض کنید دو مجموعه $T$ و $T'$ در $i$ عضو مشترکند. یال های بین این $i$ رأس و رئوسی که عضو هیچ کدام از دو مجموعه نیستند(و تعدادشان $2k+3-(2k+2-i)=i+1$ است) به رنگ $C$ هستند و بنابراین در مجموع $2i+1$ رأس هستند که دو به دو به وسیله ی یک مسیر تک رنگ $C$ به هم متصلند. بنابر فرض $2i+1 \lt k+2$ پس $i \lt \frac{k+1}{2}$ و $i \le \frac{k}{2}$.

از طرفی یال های بین رئوس دو مجموعه ی $T-T'$ و $T'-T$ نیز به رنگ $C$ هستند(اگر رأسی این ویژگی را نداشته باشد بین دو مجموعه مشترک است). این رئوس تشکیل یک مجموعه $2k+2-2i$ رأسی می دهند که هر دو عضو آن به وسیله ی یک مسیر تک رنگ $C$ به هم متصلند. بنابر فرض $2k+2-2i \lt k+2 \Rightarrow \frac{k}{2} \lt i$. که با توجه به قسمت بالا غیر ممکن است. پس فرض خلف باطل و $n(T) \ge k+2$