Задача про граф.

[codeineDreaming]

Добрый вечер, решаю задачу про граф и уже дней $5$ не могу придумать, почему граф из условия никак не может быть связным (нет, он безусловно может быть связным, но там будет слишком много рёбер, у меня есть пример на меньшее количество), хотя абсолютно уверен в этом. Подскажите пожалуйста, как тут подступиться?
Задача : В графе $300$ вершин. Оказалось, что если убрать любые $150$ вершин (вместе со всеми рёбрами), то в графе останется не менее $150$-и рёбер.
Какое минимальное количество рёбер может быть в таком графе? У меня есть пример на $750$ рёбер и я абсолютно уверен, что меньше быть не может, но как же доказать, что граф несвязный?? Я вспомнил зависимость количества рёбер от степени каждой вершины $\sum\limits_{i=1}^{n} deg(V_i) = 2R$, где $deg(V_i)$ - степень $i$-ой вершины, а $R$ - количество рёбер. Я попробовал составить граф на $749$ рёбер, исходя из зависимости, приведённой выше, я понял, что в таком случае у $298$ вершин степень должна быть $5$, а у оставшихся двух $4$ (потому что так как мы удаляем половину вершин ПРОИЗВОЛЬНЫМ образом, у нас очевидно степени вершин должны быть везде примерно одинаковым), но дальше как-то очень уж туго пробивается, думаю, тут всё намного должно быть проще и очевиднее.
Помогите пожалуйста!

[lel0lel]

Можно получить неравенство на сумму степеней вершин. Имеется столько-то способов выбрать $150$ вершин из $300$, причём в полученных графах не менее $150$ рёбер. Сложить все эти неравенства.

[codeineDreaming]

lel0lel в сообщении #1543364 писал(а):

причём в полученных графах не менее $150$ рёбер.

а как вот это получить можете подсказать?

[lel0lel]

Это есть в условии. Но я сейчас проверил, что метод не работает, так как степени вершин меняются при удалении вершин. Хотя, можно попробовать довести его до ума. Ведь удаление каких-то 150 вершин понижает сумму степеней получившегося графа на удвоенную сумму степеней удалённых вершин.

[codeineDreaming]

lel0lel в сообщении #1543366 писал(а):

Это есть в условии

я спрашивал про то, как такое ограничение задать, но понял уже.

lel0lel в сообщении #1543366 писал(а):

метод не работает

[lel0lel]

Хотя, можно попробовать довести его до ума. Ведь удаление каких-то 150 вершин понижает сумму степеней получившегося графа на удвоенную сумму степеней удалённых вершин. Ан нет, это не верно, ведь одинаковые рёбра могли соединять удалённые вершины. Надо подумать.

Попробуйте записать неравенство для случая, когда удалены первые 150 вершин.

[codeineDreaming]

lel0lel в сообщении #1543368 писал(а):

Попробуйте записать неравенство для случая, когда удалены первые 100 вершин.

1) Почему для ста? upd : обновил страницу, вопрос снят
2) Я не особо понимаю, как составить это неравенство, ведь там еще туча способов распределить степени вершин даже если мы закрепили, какие вершины удаляем, ну и сумма степеней после удаления собственно тоже будет зависеть от того, как мы изначально их раскидаем по вершинам

[lel0lel]

codeineDreaming в сообщении #1543357 писал(а):

нет, он безусловно может быть связным

А разве в условии сказано, что он должен быть связным?

[codeineDreaming]

lel0lel в сообщении #1543378 писал(а):

codeineDreaming в сообщении #1543357 писал(а):

нет, он безусловно может быть связным

А разве в условии сказано, что он должен быть связным?

а там не сказано, какой он, я придумал пример (несвязный), но мне нужно доказать, что он оптимален среди всех возможных графов, я доказал, что он самый оптимальный из несвязных графов, но не могу придумать причину, почему граф из условия не может быть связным

lel0lel в сообщении #1543378 писал(а):

codeineDreaming в сообщении #1543357 писал(а):

нет, он безусловно может быть связным

А разве в условии сказано, что он должен быть связным?

я имел в виду что условный полный граф на 300 вершин всяко оставит после себя больше 150-и рёбер

[Null]

Пусть есть граф удовлетворяющий условию. Удалим 150 раз вершину наибольшей степени(степень считается в оставшемся на этом шаге графе). Остался граф на 150 вершин и не менее 150 ребер. Теперь будем возвращать вершины в обратном порядке. Надо аккуратно посчитать сколько ребер будет добавятся минимум на каждом шаге.