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