Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

به یک رنگ‌آمیزی معتبر گراف G، متعادل می‌گوییم اگر و تنها اگر تعداد رئوس هر رنگ در آن برابر باشد. حال فرض کنید که G گرافی k-رنگی است(k3) و هیچ رنگ‌آمیزی غیر متعادل معتبری ندارد. ثابت کنید به ازای هر 3mk، دوری به طول مضربی از m در G وجود دارد.


ابزار صفحه