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