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