Простой путь, Гамильтонов путь, Гамильтонов цикл
Ошибка.
Попробуйте повторить позже
В графе 
вершина, есть гамильтонов цикл и нет треугольников. Докажите, что в этом графе есть вершина степени не более
Подсказка 1
Рассмотрим минимальный нечетный простой цикл С = a₁a₂...a_(2n+1), а множество других вершин графа за A. Что можно сказать про n?
Подсказка 2
Правильно, n ≥ 2. Рассмотрим вершину u ∈ A. Пусть есть ребра ua_i и ua_j. Что можно сказать про |i - j|?
Подсказка 3
Верно! |i - j| = 2 так, как у нас нет треугольников, и C наименьший цикл нечетной длины. Могут ли быть еще ребра из u в C?
Подсказка 4
Точно, не могут! Теперь осталось посчитать количество ребер. Сколько максимум ребер ведет из A в вершины цикла?
Подсказка 5
Верно! Максимум 2016 * 2 = 4032. Осталось только оценить минимальную степень вершины из C.
Рассмотрим наименьший простой нечётный цикл 
и множество остальных вершин 
Такой найдется, так как граф
гамильтонов. Так как нет треугольников, то 
Внутри цикла 
рёбер нет, так как он наименьший.
Пусть из вершины 
ведёт два ребра 
Так как нет треугольников, то 
(здесь смотрим по модулю 
).
Также так как 
— наименьший получаем, что 
Из этих рассуждений следует, что из 
в 
идёт максимум два ребра, так
как пусть есть рёбра 
Тогда можно расположить индексы так, что 
по модулю 
а значит
Противоречие.
Осталось посчитать рёбра. 
Тогда из 
в вершины цикла ведёт не более 
рёбер.
Тогда найдется вершина цикла степени не более, чем 
Значит есть вершина степени 
что и
требовалось.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
