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

[svv]

vatrushka в сообщении #1484255 писал(а):

мне нужно убирать ребра

Лучше так: мне можно убирать рёбра...

-- Вт сен 22, 2020 23:49:48 --

vatrushka в сообщении #1484257 писал(а):

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

Верно! Вы поняли. Оставляете по одному ребру к каждой компоненте связности, и граф остаётся связным.

vatrushka в сообщении #1484257 писал(а):

Иными словами надо доказать что у нас не более 40 компонент связности останется при удалении $V$

Верно. А теперь песня меняется. Допустим, таких частей не $3$, а $41$. Тогда обязательно найдётся часть, соединённая с вершиной $V$... как?

[vatrushka]

Тогда гарантированно есть мост через V

[svv]

Да.
А теперь рассмотрите соответствующую часть (ну, которая стала бы компонентой связности при удалении этого ребра).
Докажите, что если в этой части только вершины степени 36, 24 или сколько там по условию, из неё не может наружу торчать одно ребро (к вершине $V$).

[vatrushka]

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

[svv]

Да, правильно.

Теперь в терминах моей с Вами игры ситуация описывается так.
Пусть в случае удаления всех рёбер, инцидентных $V$, получается $Y$ компонент связности (не считая $V$).
Если $Y\leqslant 40$, Вы у меня выиграете (сможете удалить 40 ребер так, что граф останется связным).
А если $Y>40$, такой граф будет противоречить условиям задачи, и я просто не смогу его Вам предъявить.

Задача решена?

[vatrushka]

Да, я понял
Тогда наверно я распишу полный ход решения:
Исходя из четности, в графе, получаемом из исходного путем удаления вершины $V$, нету такой компоненты связности, из которой в $V$ приходит одно ребро, минимум два.
Значит компонент связности не более $\frac{80}{2} = 40$.
А так как компонент связности не более чем $40$, а степень $V$ - $80$, найдутся $40$ лишних ребер.
Ч и т д

-- 23.09.2020, 00:28 --

Большое спасибо, я бы не додумался сам.

[svv]

Верно.

vatrushka в сообщении #1484268 писал(а):

нету такой компоненты связности, из которой в $V$ приходит одно ребро

Только "компонента связности" тут в условном смысле — подграф, который стал бы отдельной компонентой связности при удалении всех инцидентных $V$ рёбер. Вы это понимаете, а преподавателю нашу условную терминологию надо пояснить, а то он посмотрит вот так:

Я потому и называл эту штуку: часть.

[vatrushka]

Я чуть чуть поправил, теперь вернее