ثابت می‌کنیم پاسخ برای $n$ فرد $\lfloor \frac{n}{2} \rfloor$ و برای $n$ زوج $\frac{n}{2}+1$ است.

درجه‌ی قرمز یک رأس را تعداد یال‌های قرمز متصل به آن تعریف می‌کنیم. به همین ترتیب درجه‌ی آبی یک رأس تعریف می‌شود.

ابتدا روشی برای رنگ‌آمیزی علی‌رضا ارائه می‌دهیم که تضمین کند حداقل به مقدار گفته شده یال آبی خواهیم داشت. برای $n$ فرد علی‌رضا یک رأس را در نظر نمی‌گیرد و بقیه‌ی رأس‌ها را به جفت‌ها افراز می‌کند. او یال بین دو رأس هر جفت را آبی و بقیه‌ی یال‌ها را قرمز می‌گذارد. در ابتدا درجه‌ی آبی هر رأس فرد است و طی اعمال تعویض، زوجیت درجه‌ی آبی رأس‌ها تغییری نمی‌کند؛ پس فرهاد هر طوری که بازی کند، در انتها درجه‌ی آبی تمام رأس‌ها فرد خواهد بود و دست کم

$\lfloor \frac{n}{2} \rfloor$ یال آبی خواهیم داشت.

برای $n$ زوج علی‌رضا یال رأس شماره‌ی ۱ به رئوس $2, 3, 4$ را آبی می‌گذارد. او هم‌چنین بقیه‌ی رأس‌ها را به جفت‌هایی افراز کرده و یال بین دو رأس هر جفت را آبی می‌کند و در انتها بقیه‌ی یال‌ها را قرمز می‌گذارد. طی اعمال تعویض، علاوه بر زوجیت درجه‌ی آبی رئوس، زوجیت تعداد یال‌های آبی نیز ثابت می‌ماند. بنابراین فرهاد هر طوری بازی کند در انتها درجه‌ی تمام رئوس فرد خواهد بود و امکان ندارد درجه‌ی تمام رئوس برابر ۱ شود؛ زیرا در این صورت زوجیت تعداد یال‌های آبی تغییر کرده است که تناقض است. پس در انتها دست کم $\frac{n}{2} + 1$ یال آبی خواهیم داشت. $\blacksquare$

اکنون ثابت می‌کنیم به ازای هر دور به طول زوج مانند $C$، فرهاد می‌تواند تعدادی عمل تعویض انجام دهد؛ طوری که رنگ یال‌های $C$ تغییر کند؛ امّا رنگ هیچ یال دیگری تغییر نکند. حکم را به استقرای ضعیف روی $k$ (طول دور $C$) ثابت می‌کنیم.

برای پایه‌ی استقرا $k=4$ را در نظر بگیرید. فرض کنید $C=v_1v_2v_3v_4v_1$ باشد. مسیری گذرنده از تمام رئوس دیگر مانند $P$ در نظر بگیرید. فرهاد می‌تواند یک بار با عمل تعویض روی دور $v_4Pv_1v_3v_2v_4$ و بار دیگر عمل تعویض روی دور $v_4Pv_1v_2v_3v_4$ کاری کند که رنگ یال‌های $C$ تغییر کند؛ امّا رنگ هیچ یال دیگری تغییر نکند. به این ترتیب پایه‌ی استقرا ثابت می‌شود.

حال فرض کنید حکم برای $k$ برقرار باشد. ثابت می‌کنیم حکم برای $k+2$ نیز برقرار است. دور $C=v_1v_2\ldots v_{k+2}$ را در نظر بگیرید. فرهاد می‌تواند رنگ یال‌های دور $v_1v_2v_3v_4v_1$ را مستقل از بقیه‌ی یال‌ها طبق پایه‌ی استقرا تغییر دهد. هم‌چنین او طبق فرض استقرا می‌تواند رنگ یال‌های دور $v_3v_4v_5\ldots v_{k+2}v_3$ را مستقل از بقیه‌ی یال‌ها تغییر دهد. با این دو تغییر، رنگ یال‌های دور $C$ مستقل از بقیه‌ی یال‌ها تغییر می‌کند و حکم استقرا ثابت می‌شود. $\blacksquare$

حال فرض کنید $n$ فرد باشد. ثابت می‌کنیم فرهاد می‌تواند رنگ یال‌های یک دور به طول ۳ را مستقل از بقیه‌ی یال‌ها تغییر دهد. فرض کنید $C=v_1v_2v_3v_1$ یک دور به طول ۳ باشد و $P$ مسیری گذرنده از بقیه‌ی رئوس باشد. فرهاد می‌تواند یک بار با تغییر رنگ دور همیلتونی $v_1Pv_2v_3v_1$ و سپس با تغییر دور به طول زوج $v_1Pv_2v_1$ به هدف خود برسد. $\blacksquare$

حال ثابت می‌کنیم فرهاد می‌تواند به ازای هر رنگ‌آمیزی اولیه طوری بازی کند که تعداد یال‌های آبی حداکثر به میزان گفته شده باشد.

اگر $n$ فرد باشد، فرهاد می‌تواند در هر لحظه یک رأس $v$ با درجه‌ی آبی بیش‌تر از ۱ در نظر بگیرد. $v$ شامل دست کم دو هم‌سایه مانند $a, b$ است که با یال آبی به $v$ وصل هستند. فرهاد با تغییر رنگ دور به طول ۳ شامل رئوس $v, a, b$ می‌تواند تعداد یال‌های آبی را کم کند. این روند پایان‌پذیر است و بالأخره به وضعیتی می‌رسیم که درجه‌ی آبی هر رأس حداکثر ۱ است و در چنین شرایطی حداکثر $\lfloor \frac{n}{2} \rfloor$ یال آبی خواهیم داشت.

اگر $n$ زوج باشد، فرهاد در هر یک از چهار حالت زیر، می‌تواند تعداد یال‌های آبی را کم کند:

• مسیری آبی به طول دست کم سه داشته باشیم. در این صورت فرهاد با تغییر رنگ یال‌های دوری به طول ۴ شامل این مسیر، تعداد یال‌های آبی را کم می‌کند.
• رأسی مانند $v$ با درجه‌ی آبی بیش‌تر از ۳ داشته باشیم. $v$ شامل دست کم چهار هم‌سایه‌ مانند $a, b, c, d$ است که با یال آبی به $v$ وصل هستند. ابتدا فرهاد رنگ یال‌های دور $vbcav$ را تغییر می‌دهد. اگر تعداد یال‌های آبی کم شود که به هدف خود رسیده‌ایم؛ در غیر این صورت تعداد یال‌های آبی تغییری نکرده است و یال‌های مسیر سه یالی $bavd$ آبی می‌شود که طبق حالت قبل می‌توان تعداد یال‌های آبی را کم کرد.
• دوری آبی به طول ۳ مانند $abca$ داشته باشیم. در این صورت اگر یال آبی دیگری نداشتیم، تعداد یال‌های آبی از مقدار گفته شود بیش‌تر نیست و حکم مسئله اثبات شده است؛ در غیر این صورت یک یال آبی دیگر مانند $uv$ در نظر بگیرید. اگر $uv$ رأس مشترک با دور داشته باشد، حالت یکم پیش می‌آید و می‌توان تعداد یال‌های آبی را کم کرد. در غیر این صورت ابتدا رنگ یال‌های دور $abuva$ را تغییر می‌دهیم. اگر تعداد یال‌های آبی کم شود که به هدف خود رسیده‌ایم؛ در غیر این صورت تعداد یال‌های آبی ثابت می‌ماند و مسیری آبی به طول سه ایجاد می‌شود ($vacb$) که طبق حالت یکم می‌توان تعداد یال‌های آبی را کم کرد.
• دو رأس $u, v$ با درجه‌ی آبی بیش‌تر از ۱ داشته باشیم. اگر $u, v$ به هم یال آبی داشته باشند، یکی از حالات یکم یا سوم پیش می‌آید که به هدف خود می‌رسیم؛ در غیر این صورت $u$ و $v$ هر کدام دست کم دو هم‌سایه مانند $u_a, u_b$ و $v_a, v_b$ دارند که با یال آبی به آن‌ها وصل هستند. فرهاد می‌تواند با تغییر رنگ یال‌های دور به طول زوج $uu_av_avv_bu_bu$ تعداد یال‌های آبی را کم کند.

فرهاد تا زمانی که دست کم یکی از سه حالت بالا در گراف وجود دارد، تعداد یال‌های آبی را کم می‌کند. با توجه به پایان‌پذیر بودن این فرآیند، بالأخره به وضعیتی می‌رسیم که سه حالت بالا در گراف وجود نداشته باشند. در این وضعیت درجه‌ی آبی حداکثر یک رأس می‌تواند بیش‌تر از ۱ باشد (که خود آن نیز حداکثر ۳ است). در این صورت تعداد یال‌های آبی حداکثر $\frac{n}{2}+1$ خواهد شد و حکم اثبات می‌شود. $\blacksquare$