خب با استقرا اثبات می کنم. پایه n=1 که درسته.

فرض کنید برای n-1 هم درسته.

حال یک گراف n راسی در نظر بگیرید . یک راس دلخواه را کنار می گذاریم حال اگه با انجام عملیات برای n-1 راس این راس هم سیاه شد که هیچ .اگر نشد این کار را بزای تمام ریوس مس توان تکرار کرد که در صورتی که به خواسته ی مسیله نرسیدیم پس عملیاتی وجود دارد که برای هر راس p رنگ تمام ریوس به جز p را می توان عوض کرد ازین پس وقتی میگم کار یا حرکت منظورم این کاره.

مسیله به دوحالت تقسیم می شه اگر n زوج بود اینکار را برای هر راس تکرار می کنیم چون هر راس n-1 بار رنگ عوض کرده پس در اخر تمام ریوس سیاهند. حال اکر nفرد بود.یک راس زوج به نام v حتما وجود دارد این راس و تمام همسایه هایش را s مینامیم حال اگر این حرکت را برای تمام ریوس درون s انجام دهیم تمام ریوس بیرونی رنگشان عوض شده و s تماما سفید مانده حال این حرکت را برای راس v انجام می دیم وتمام گراف سیاه می شه.

بفرمایید اینم راه حل البته می توان اثبات کرد که به تمام حالت های رنگ امیزی می توان رسید ولی اثبات سخت تر است. اون سوالو خودم می ذارم

آقا این راه‌حلی که من دارم یه کم طولانیه، شاید راه‌حل کوتاه‌تری هم باشه، اما من همین راه حل طولانی رو می‌گم چون جنبه‌ی آموزشی داره. البته خیلی وارد جزییات نمی‌شم که طولانی نشه.

قسمت۱: تبدیل کردن مساله‌ گراف به مساله $n$معادله و $n$مجهول

یه روش خوب برای حل این مسايل اینه که اینا رو تبدیل کنیم به $n$معادله و $n$مجهول به پیمانه‌ی دو. برا ی اینکه منظورم رو بفهمید برای این مساله این جوری می‌شه:

ما در نهایت هر راس رو یا تغییر رنگ دادیم یا ندادیم (اگه دو بار تغییر رنگ بدیم، انگار که اصلا تغییر رنگ ندادیم). بنابراین می‌تونیم $x_i$ رو تعریف کنیم آیا راس $i$ام تغییر رنگ داده یا نه. حالا برای اینکه مطمئن شیم در نهایت هر راسی فردبار تغییر رنگ داده، باید ممطمئن باشیم $xor$ همه‌ی راس‌هایی که با این راس مجاور هستند با خود این راس برابر ۱ می‌شود. پس به ازای هر راسی یه معادله‌ی این شکلی داریم: $x_{i_1} \oplus x_{i_2} \oplus ... x_{i_k} = 1$

اگه این $n$تا معادله رو بنویسیم، به یک دستگاه $n$معادله و $n$مجهولی به پیمانه‌ی ۲ می‌رسیم (چون همه چی xor هست اصطلاحا گفته می‌شه پیمانه‌ی ۲). بنابراین از اینجا به بعد ما باید نشون بدیم این دستگاه معادلات حداقل یک جواب دارد. یعنی می‌شه جوری مقادیر $x_i$ها رو صفر یا یک گذاشت که در نهایت به ازای هر راس، حاصل xor خودش و همه‌ی همسایه‌هاش یک بشه.

مثلا برای یک گرافی که شماره‌های رئوسش ۱ و ۲ و ۳ هستند و راس ۱ به راس ۲ و ۳ متصل هست، دستگاه معادلات این شکلی می‌شه:

$x_1 \oplus x_2 \oplus x_3 = 1$

$x_1 \oplus x_2 = 1$

$x_1 \oplus x_3 = 1$

قسمت ۲: بررسی روش حل مساله $n$معادله و $n$مجهول

برای حل دستگاه معادلات خطی یکی از روش‌های معمول روش حذف گاوسی است که معمولا در مدارس برای حل ۳معادله-۳مجهول به بچه‌ها آموزش می‌دن. تو این روش می‌یان توی هر معادله، به جز یک متغیر، ضریب بقیه‌ی متغیرها رو صفر می‌کنن. این کار با جمع کردن معادله‌ها با هم دیگه انجام می‌دن.

مثلا برای دستگاه معادلات بالا، اگه معادله‌ی اول و دوم رو جمع کنیم، به معادله‌ی $x_3=۰$ می‌رسیم (دقت کنید که عملگرمون xor هست). اگه اولی و سومی رو جمع کنیم به معادله‌ی $x_2=۰$ می‌رسیم. اگه هر سه تا رو با هم جمع کنیم به معادله‌ی $x_1=1$ می‌رسیم.

حذف گاوسی در واقع یه الگوریتمی است که با اعمال اون رو هر دستگاه $n$ معادله و $n$ مجهول می‌شه به دستگاهی رسید که توی هر معادله‌اش، حداکثر یک متغیر وجود داشته باشه و بنابراین به راحتی بشه دستگاه رو حل کرد! توصیه می‌کنم اگه روش رو بلد نیست حتما یادش بگیرید.

قسمت ۳: اثبات اینکه همیشه دستگاه جواب داره

تو این مساله روش حذف گاوسی اگه بخواد برای دستگاه معادلات xorای که ساختیم به جواب نرسه، به یه معادله‌ای می‌رسه که ضریب همه‌ی متغیرهاش صفر شدن ولی باید حاصل جمع اونها یک بشه. ما باید ثابت کنیم همچین اتفاقی نمی‌افته (برهان خلف).

فرض کنیم همچین اتفاقی افتاد. یعنی باید تعدادی از معادلات اولیه‌مون باشند که اگه با هم جمع‌شون کنیم (درواقع xor کنیم)، سمت چپ معادله هیچ متغیر باقی نمونه و سمت راست حاصلش یک بشه. چون $n$تا معادله‌ی اولیه که داشتیم، سمت راست همه‌شون یک بوده، پس باید فردتا‌معادله‌ی اولیه باشن که xor سمت چپ‌شون صفر شده و xor سمت راست‌شون یک شده.

اما چون دستگاه معادلات از روی گراف ساخته شده، اگر $x_i$ در سمت چپ معادله‌ی $j$ام باشد، $x_j$هم در سمت چپ معادله‌ی $i$ هست. از طرفی هر راس توی معادله‌ی متناظر خودش هم قرار داره. اگه همه‌ی این‌ها رو با هم جمع کنیم، چون فردتا معادله داشیم، در کل فردبار از $x_i$هایی خواهیم داشت که معادلات‌شون انتخاب شدن. بنابراین هیچ وقت سمت چپ حاصل جمع این معادلات صفر نمی‌شه و حداقل ضریب یکی از متغیرها باید یک باشه. (اگه این تیکه‌اش مبهمه، لازمه خودتون روی کاغذ یه کمی فکر کنید تا درکش کنید)