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