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