Сколько студентов останется после сессии?

[melnikoff]

На курсе 100 студентов. Известно что среди них можно выделить 149 различных пар студентов, которые во время семестра давали друг другу списывать на контрольных. Деканат принял решение отчислить после сессии минимально возможное число студентов, но таким образом, что среди оставшихся студентов не осталось ни одной пары списывающих у друг друга.
Найдите наибольшее и наименьшее количество студентов, которые останутся к следующему семестру.

Мое решение:
Легко видеть, что максимальное кол-во оставшихся студентов равно 98. 99 студентов остаться не может, так как единственный исключенный может оборвать не более 99 ребер в графе, а их по условию 149. А для 98 оставшихся мы можешь предъявить конкретный граф: 1-й связан со всеми, 2-й связан с любыми 50-ю (не считая первого). Тогда, исключив первых двух, у нас оборвутся все 149 ребер.
А вот с минимальным количеством оставшихся студентов у меня возникли трудности.
Интуиция мне подсказывает, что нужно плясать от паросочетаний, так как в паросочетании удаление одной вершины обрывает не более одного ребра, и для обрыва определенного кол-ва ребер мы можем максимизировать кол-во отчислений. Однако, максимальное паросочетание в полносвязном графе со 100 вершинами имеет лишь 50 ребер, что меньше 149. А это означает, что паросочетание не подойдет, но возможно подойдет граф с подпаросочетанием (типа, как подмножество). Дело в том, что связная пара вершин недостаточно "утилизирует" кол-во ребер (всего 1 ребро на 2 вершины).
Тогда давайте рассмотрим полносвязные тройки (тройки между собой несвязны) - 3 ребра на 3 вершины - уже лучше, но все равно недостаточно.
Тогда давайте рассмотрим полносвязные четверки. Точнее, имеем 24 полносвязные четверки (96 вершин и 144 ребер) и одну четверку полносвязную без одного ребра (4 вершины и 5 ребер). Что бы в каждой полносвязной вершине оборвать все ребра, нужно отчислить 3 вершины и последней "неполноценной" четверке нужно отчислить 2 вершины. Итого, имеем $3\cdot 24 + 2 = 74$ отчисленных вершин. Очень похоже максимальное необходимое кол-во отчислений, после которого останется 26 студентов (это минимальное оставшееся число студентов).

Рассуждения очень "сырые". Как рассуждать более правильно и строго? И вообще, правильно ли я рассуждаю?

[Sender]

Вам нужно найти размер наибольшего наименьшего вершинного покрытия( ) в графе на ста вершинах со $149$ рёбрами. Полагаю, в этом могут оказаться небесполезными тождества Галлаи.

[melnikoff]

Sender в сообщении #1525674 писал(а):

Вам нужно найти размер наибольшего наименьшего вершинного покрытия( ) в графе на ста вершинах со $149$ рёбрами.

Почитал и узнал что такое вершинное покрытие графа.
ИМХО, ваша, Sender, формулировка неверна.
Скорее, правильно так: Нужно найти на множестве всех графов со 100 вершинами и 149 ребрами минимальное минимальное вершинное покрытие и максимальное минимальное вершинное покрытие.

[mihaild]

Нет, если хотят отчислить как можно меньше студентов, то именно наибольшее наименьшее. Максимальное минимальное было бы если бы хотели отчислить так, что никого из отчисленных оставить, не отчислив кого-то еще, нельзя.

[Geen]

melnikoff в сообщении #1525650 писал(а):

Тогда давайте рассмотрим полносвязные четверки.

А если рассмотреть графы, у которых индекс вершин не превосходит трёх?..

[melnikoff]

mihaild в сообщении #1525691 писал(а):

Нет, если хотят отчислить как можно меньше студентов, то именно наибольшее наименьшее. Максимальное минимальное было бы если бы хотели отчислить так, что никого из отчисленных оставить, не отчислив кого-то еще, нельзя.

А разве "наибольшее наименьшее" и "максимальное минимальное" -- это не синонимы?

[mihaild]

melnikoff в сообщении #1525907 писал(а):

А разве "наибольшее наименьшее" и "максимальное минимальное" -- это не синонимы?

Насколько я понимаю, наиболее распространенная терминология тут: множество максимальное, если к нему нельзя ничего добавить, и наибольшее, если нет большего размера. Наибольшее автоматически максимально, обратное, вообще говоря, неверно.