رنگ کردن یالهای یک چند وجهی مثلثی

[amir.ekhlasi]

یک چند وجهی مثلثی داریم. ثابت کنید میتوان یالهایش را با دو رنگ آبی و قرمز رنگ زد، به طوری که از هر رأس به رأس دیگر، یک مسیر تکرنگ قرمز و یک مسیر تکرنگ آبی موجود باشد.

 

[darrande]

پاسخ : رنگ کردن یالهای یک چند وجهی مثلثی

روی تعداد وجوه استقرا بزن
برای چهار تا وجه وجودد داره
فرض بر اینه که برای nهم هست برای n+1هم اینطوری ثابت میکنیم که
یه وجه دلخواه رو بگیر سه تا یال به این وجه وارد میشه ،بدون اینکه از مسئله چیزی کم شه دو تا رو آبی و یکی رو قر مز بگیرید پس در این وجه ما یالی که بین دو راسی که آبی بهشون وارد میشه رو قرمز اون دو تا رو آبی میکنیم.