بابا سوال آسون تر این حرفاست راهش کوتاهه...

n+1 راس رو ببرین دسته 1 و n-1 راس باقمیمونه هم ببرین دسته 2.حالا هر مرحله تو دسته 1 یه جاده خاکی رو بگیرین و n-1 راس باقیمونده از دسته 1 رو با کل راس های دسته 2 یه تطابق دلخواه بزنین.

پس از تعدادی مرحله همه جاده های دسته اول آسفالت میشه.حالا دوتا راس دلخواه از دسته 1 رو ببرین دسته 2 و برای دسته 2 هم همون کار رو که برا دسته 1 کرده بودیم انجام بدین.

گرافی با $2n$ راس در نظر بگیرید که هر راس بیانگر یکی از شهرهاست ، بین راس $i$ و راس $j$ یال میگذاریم ، اگرو فقط اگر بین این دوشهر جاده خاکی وجود داشته باشد .

لم ) اگر گراف جاده های خاکی ، گرافی دوبخشی باشد ، مسئله حل شده است .

در اینصورت رئوس موجود در هر بخش ، دو به دو با جاده آسفالت به هم متصل اند ، پس گراف به دوبخش با شرایط سوال تقسیم می شود .

ابتدا گراف را به شکل دلخواه به دو دسته ، هر یک شامل $n$ راس تقسیم می کنیم ، فرض کنید در دسته اول $x$ یال و در دسته دوم $y$ یال $(x>y)$ داشته باشیم .روشی ارائه می دهیم که کلیه یال ها درون این بخش ها را حذف کنیم.، اگر هم $x$ و هم $y$ از بزرگتر از 0 باشند در اینصورت در هر مرحله یک یال در هر دوبخش حذف می کنیم ، $n-2 $ یال باقی مانده رو هم به دلخواه $n-2 $راس در یک بخش را به $n-2$ راس در بخش دیگر وصل می کنیم ( دقت کنید این یال های بین دوبخش هیچ اهمیتی ندارند) ، بنابراین پس از مدتی به این وضعیت می رسیم که در یک دسته دوم 0 یال ، و در دسته اول $x-y$ یال داریم (اگر در ابتدا $x=y$ بود که مسئله حل شده است)

اکنون روش جدید ارائه میدهیم ، در هر مرحله 1 یال از بخش اول و دو راس دلخواه از دسته دوم انتخاب می کنیم و $n-2$ یال را نیز به دلخواه از$n-2$ راس بخش اول و $n-2$ راس بخش دوم انتخاب میکنیم ، تعداد یال های درون دسته ها تغییر نمی کند ، ولی در دسته دوم 1 یال و در دسته اول $x-y-1$ یال داریم ، سپس روش قبل را یکبار انجام میدهیم و دوتا از تعداد یالهای بین دسته ها کم میشود ، بنابراین پس از این عملیات ، یا همه ی یال های بین دسته ها از بین می روند که مسئله حل میشود یا تنها در یکی از دسته ها یک یال می ماند .

این یال را در نظر می گیریم ،یکی از راسهای دو سر این را در نظر میگیریم ، اگر هیچ یالی به دسته دیگر نداشته باشد ، در اینصورت مسئله حل میشود (این راس را وارد بخش دیگر میکنیم)

فرض کنید این راس ، $t$ تا یال به دسته دیگر داشته باشد ، $t$ مرحله به این شکل انجام میدهیم که هر مرحله 1 یال از این $t$ یال را انتخاب و $n-1$ یال دیگر را به دلخواه از $n-1$ راس دو بخش انتخاب میکنیم ، بنابراین در این حالت هم مسئله حل میشود !

ابتدا گراف را تشکیل می دهیم به این صورت که به ازای هر شهر یک راس و به ازای هر جاده خاکی یال قرمز و به ازای جاده آسفالت یال آبی می گذاریم.

لم) گراف زوج راسی k منتظم با یال های یکرنگ تطابق کامل دارد.

اثبات لم) هر بار یال راس u را با یکی از همسایه هایش می گیرم در زوج راس دیگه درجه هرراس k است و می توانم از فرض استقرا استفاده کنم.

لم1)اگر تمام یال های گراف کامل 2n راسی یک رنگ باشد می توان تمام یال ها را با استفاده از عملیات سوال ( گرفتن تطابق کامل ) به رنگ دیگر درآورد.

اثبات لم1) با استفاده از لم هر بار یک تطابق کامل گرفته یال های انرا آبی کرده و حدف می کنیم درجه هرکی 1 واحد کم شده ومیتوان از لم استفاده کرد.

لم2)در گراف کامل زوج راسی می توان تمام یال های یک راس دلخواه را با استفاده از عملیات سوال ( گرفتن تطابق کامل ) آبی کرد .

اثبات لم2 ) هر بار این راس دلخواه را با یکی از همسایه هایش می گیرم که یال قرمز دارد و باقی تطابق را دلخواه می گیرم هربار یال های قرمز متصل به راس دلخواه کم می شود تا تمام شود.

اثبات سوال

پایه استقرا ) بدیهی گراف 2 راسی.

فرض استقرا ) هر گراف کامل 2n راسی با یال های آبی و قرمز را میتوان به دو دسته (نه لزوما برابر) افراز کرد طوری که یال های هر دسته همه آبی باشد.

حکم استقرا ) با استفاده از فرض برای هر گراف کامل 2n+1 راسی نیز اثبات کنید.

اثبات حکم استقرا ) با استفاده از لم2 یال های راس u را آبی می کنیم.حال سه حالت به وجود می آید:

i)تمام یال ها به غیر از یال های متصل به u قرمز است.برای حل این قسمت در باقی راس ها یال راس v را با u همیشه گرفته و باقی یال های راس های دیگر را طبق لم1 می توان آبی کرد.هال تمام راس هارا به غیر از v را در یک دسته و v را در یک دسته دیگر می گداریم ( بدیهی درست !!!!)

ii)حداقل یک یال آبی در بین تمام یال ها به جزیال های متصل به u وجود.برای حل این قسمت فرض کنید یال بین دو راس x و y آبی باشد حال این طور عمل می کنیم که 2راس x و u با هم میگریم و در 2n راس دیگه می توان طبق لم2 یال های متصل به راس y را آبی کرد حال دو راس u و y را کنار گداشته و در 2n راس باقی طبق فرض استقرا می توان به دو دسته افراز کرد حال دو راس uوy در دسته ای می ذاریم که x در آن نباشد( بدیهی درست !!!!)

iii)تمام یال ها به غیر از یال های متصل به u آبی است.( بدیهی درست !!!!)