Предположим, есть такое подмножество. Сколько дуг из него выходит? А сколько входит в образ?
Какое подмножество Вы имеете ввиду? Что такое <<дуги>>?
А как насчёт моих исправлений в варианте доказательства?
Выберем произвольно множество
вершин доли
графа
. Допустим противное:
, тогда в
выберем какие-нибудь
вершин, тогда по условию задачи для любых выбранных вершин найдутся
смежных вершин из
. Теперь рассмотрим какую-нибудь оставшуюся вершину из
, отличную от ранее выбранных. Она, как несложно понять, уже не может быть смежной ни с какой из вершин множества, поскольку все вакантные степени вершин
заполнятся, следовательно, предположение неверно, и всё хорошо.