Задача по теории графов

[vatrushka]

В связном графе вершина v имеет степень 80, девяносто вершин имеют степень 24, остальные вершины имеют степень 36. Доказать, что существует 40 рëбер, инцидентных v, удаление которых оставляет граф связным.
Может кто - то что то подскажет?
У меня никаких идей, единственное что идет в голову это теорема о том что если в графе ребер больше чем $\frac{(n-1)(n-2)}{2}$, то он связен, но тут это особо не применить, то есть можно это применить и получить доказательство для каких то маленьких $n$ возможно.
Но в общем и целом я решения не вижу
Буду благодарен советам.
Спасибо
(Задача из вступительного в CS center за 2018 год, на экзамене не решил и сколько над ней думал все еще не решил)

[vpb]

Могу только посоветовать подумать над родственной задачей: докажите, что не существует графа из 11 вершин, в котором каждая вершина имеет степень 3.

[vatrushka]

Не, ваша задача решается легко ибо сумма степеней всех вершин графа четна, а в вашем графе $11 \cdot 3 = 33$ - нечетна

[vpb]

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

[vatrushka]

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

[svv]

Попробуем рассуждать от противного. Пусть существует такой граф (удовлетворяющий условиям), что удаление любых $40$ рёбер, инцидентных $v$, превращает граф в несвязный.

Удалим все $80$ рёбер, инцидентных $v$. Поинтересуемся, на какое число компонент связности (не считая самой вершины $v$) распадётся граф. Можно ли считать, например, что это число равно $5$ или $10$?

-- Вт сен 22, 2020 00:07:20 --

Есть идеи?

[vatrushka]

Не знаю, что то нету
Суммарное число ребер будет $\frac{90 \cdot 24 + 36 \cdot x - 80}{2}$ на $90+x$ вершинах если удалить те 80

-- 22.09.2020, 20:47 --

Так, я что то начал понимать
Если разделить на 5 частей, то по принципу дирихле будет группа из $\frac{90 + x}{5}$ вершин, при этом в ней будет вершина со степенью 24, значит
$\frac{90 + x}{5} >= 24$

[svv]

Попробую сформулировать, чего я хочу от Вас, в форме игры.

Представьте, что мы с Вами играем в такую игру. Я предъявляю Вам граф, удовлетворяющий условиям. Вы удаляете 40 рёбер из 80, инцидентных $v$. После чего игра заканчивается.
Если граф получается НЕсвязным, выигрываю я. Если связным, выигрываете Вы.
Моя цель — предложить Вам такой граф, что какие 40 рёбер Вы ни удалите, граф распадётся на части.
Ваша цель — выбрать такие 40 рёбер, чтобы граф на части не распался.

Я предлагаю Вам вот какой граф. Если убрать все $80$ рёбер, инцидентных $v$, он распадётся на 3 компоненты связности $A,B,C$ (не считая самой вершины $v$). Как устроены эти части, значения не имеет. Для пущей конкретики — пусть известно, что вершину $v$ соединяют с частями $A,B,C$ соответственно $37$,$41$ и $2$ ребра. Сможете выиграть?

Задача-максимум: покажите, что при 3 частях при правильной игре (какой именно?) Вы у меня выиграете всегда.

[vatrushka]

Не, ну если там есть три части, не связанные друг с другом, то это легко, по принципу дирихле к какой то из частей идет меньше 40.
То есть нужно доказать что V - почему то точка сочленения как минимум

[svv]

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

[vatrushka]

Я немного перепутал, сейчас подумаю еще

[svv]

В данном случае это совсем легко, но важен общий принцип.

[vatrushka]

А, наоборот, мне нужно убирать ребра, что бы к каждой части оставалось по ребру
Тоесть к С - одно, к А - 36, к Б - 40

[svv]

Верно. Всего Вам нужно убрать только 40 рёбер, так что не обязательно убирать столько, сколько Вы написали, где-то получится меньше.

Но прочувствуйте общий принцип: выбираете одно ребро, идущее к $A$, одно ребро, идущее к $B$ и одно ребро, идущее к $C$. Их не трогаете. А удаляете сколько угодно рёбер из оставшихся.

Это хорошо поняли?

[vatrushka]

Если убрав эту вершину у нас получится не более 40 компонент связности, то тогда есть 80-40 ребер, которые можно спокойно удалить
Иными словами надо доказать что у нас не более 40 компонент связности останется при удалении $V$
Получается если степень вершины $X$, а компонент связности при удалении $V$ - $Y$ штук, то можно спокойно удалить $X - Y$ ребер