Принцип крайнего
Ошибка.
Попробуйте повторить позже
В графе с 
вершинами нет петель и кратных рёбер. При этом степень каждой вершины не более 
Докажите, что вершины графа
можно раскрасить в 
цветов так, чтобы не более чем у 
рёбер совпали цвета концов.
Назовём ребро, у которого совпали цвета концов, плохим. Рассмотрим раскраску, в которой наименьшее количество плохих рёбер.
Предположим, что в этой раскраске нашлась вершина 
из которой выходят как минимум 
плохих ребра. Посмотрим на все рёбра,
выходящие из 
По принципу Дирихле существует цвет, в который окрашены не более трёх рёбер, выходящих из 
Покрасим 
в этот
цвет. Тогда мы избавились как минимум от 
рёбер, а получили не более трёх, то есть уменьшили их количество хотя бы на один. Это
противоречит выбору раскраски.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
