سلام ! ( ;

خب استقرای قوی میزنیم . روی رئوس.
پایه » n = 2 (واضحه که راس مطلوب وجود داره ، راسی که وارد راس دوم میشه)
فرض » هر تورنمنت با کمتر از k راس ، چنین راس مطلوبی داره .
حکم » همون فرض منتها با k راس.

یک تورنمت k راسی رو در نظر میگیریم . راس N رو ازش حذف میکنیم . حالا توی تورنمت باقی مونده طبق فرض استقرا میدونیم راس مطلوبی به اسم V داره که به تمام رئوس مسیری تک رنگ داره . حالا اگه V به N وارد شده باشه خب حکم استقرا ثابت شده ( چرا ؟ ) در غیر اینصورت میدونیم N به V وارد شده . خب میتونیم بدون تغییر در کلیت سوال فرض کنیم رنگ یال n -> v هست قرمز .

لم 1
اگه B مجموعه رئوسی باشه که V به اونها مسیر تک رنگ آبی و R مجموعه رئوسی باشه که V به اونا مسیر تک رنگ سرخ داره ، در اون صورت :

لم 1.1اگر راسی از مجموعه ی B به راس N یال آبی داشته باشه (از B به N ) اونوقت V به N هم مسیر تک رنگ داره و حکم ثابته .

لم 1.2اگر حتی یک راس از مجموعه ی R به راس N یال سرخ داشته باشه (از R به N)اونوقت V به N هم مسیر تک رنگ داره و حکم ثابته.

دلیل درستی لم های بالا رو میتونید توی شکل زیر بررسی کنید ( از یالهای متصل به N فقط یکیشو رسم کردم پس باید از تخیلتون هم بهره بگیرین) »

راه درست » بسیار خب ، میتونیم مجموعه ی B به همراه راس N رو در فرض استقرا به کار ببریم ( یا بهتره بگم فرض استقرا رو در اونا به کار ببریم )
حالا طبق فرض استقرا راس مطلوب U بین رئوس مجموعه B + N وجود داره به طوری که به بقیه رئوس مجموعه مسیر تک رنگ داره

دو حالت وجود داره
اگر U = N » در این صورت N راس مطلوب مجموعه کلیه . چون به V یال سرخ وارد کرده و از طریق V هم به تمام رئوس مجموعه R مسیر داره و حکم ثابته

اگر U = N نبود » در این صورت میدونیم U به N مسیر تک رنگ داره ، اگه این مسیر سرخ بود خب از طریق N میتونه به V و R هم مسیر داشته باشه و اینجوری به کل رئوس مسیر تک رنگ داره و U میشه راس مطلوب

اگه مسیر U به N آبی بود ، در اون صورت میشه گفت V راس مطلوب کل رئوسه .. ( چرا ؟ الان میگم ) میدونیم U عضو B هست . میدونیم B مجموعه رئوسیه که V به اونا مسیر آبی داره ، پس اگه یکی از اعضای B به N مسیر آبی داشته باشه پس V به N هم مسیر تک رنگ (آبی ) داره و میشه راس مطلوب !

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

راه غلط رو پاک نمیکنم چون خیلی ها فکر کردن درسته و اینجوری میتونن با خوندن این متن متوجه اشتباهشون بشم

راه غلط »
توضیح 1 : خب ، مجموعه رئوس B رو در نظر بگیرین . اگر B تهی باشه ، اونوقت حکم ثابته و راس N به عنوان راس مطلوب شناخته میشه که به تمام رئوس مسیر تک رنگ داره ( چرا ؟ توی شکل بالا کافیه مجموعه B رو حذف شده در نظر بگیرین تا بفهمید )

اگر B حداقل شامل یک راس باشه ، در اون صورت میتونیم فرض استقرا رو برای تمام رئوس B در نظر بگیریم . (چرا ؟ )
پس طبق فرض استقرا راس مطلوب U در مجموعه B وجود داره به طوری که به تمامی رئوس مجموعه B مسیر تک رنگ داره .

حالا ثابت میشه که طبق لم 1.1، راس U به راس N وارد شده ، و اون یال قرمزه . خب اینکه یال U -> N قرمزه که خیلی بدیهیه ( به لم 1.1 نگاه کنید ) البته در صورتی که یال U -> N باشه نه N -> U . خب ، چاره اینه که مجموعه ی B رو مجموعه ای فرض کنیم که هم از V به اونها مسیر آبی وجود داشته باشه و هم اینکه راس N به اونها وارد نشده باشه. خب حالا که ثابت کردیم از U به N یک یال سرخ وارد میشه ، پس از طریق N میشه به V رفت ( شکلو نگاه کنید ) بعد از V هم میشه به R رفت ( با حرکت روی مسیر های سرخ )

خب در اون صورت U همون یال مطلوبه که به همه رئوس مسیر تک رنگ داره ... پس حکم ثابت شد !

( ببخشید زیادی شهودی شد اگه کسی چیزی نفهمید بگه تا توضیح بدم... ولی چیزی که مطمئنم درستی این اثباته )