المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۱:ترکیبیات:سوال ۲

سوال ۲

یال‌های گراف ‎$K_{16}$‎ را با دو رنگ قرمز و آبی رنگ کرده‌ایم به طوری که اختلاف تعداد یال‌های قرمز و آبی حداقل هشت تاست. ثابت کنید یا یک ‎$K_{2,5}$‎ قرمز وجود دارد یا یک ‎$K_{2,5}$‎ آبی. گراف ‎$K_{2,5}$‎ گراف دوبخشی کامل است با دو بخش دو‌ رأسی و پنج رأسی که در آن، هر رأس بخش اول با تمام رئوس بخش دوم مجاور است.


ابزار صفحه