Невычислительная задачка по теории графов.

[Мастак]

Цитата:

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

PS Город - вершина. Дорога между городами - ребро.

Как подступиться подскажите, плиз, чтобы "не изобретать велосипедов"!

[mihaild]

Мастак в сообщении #1525458 писал(а):

есть вершина степени 100

Мастак в сообщении #1525458 писал(а):

степень каждой вершины равна 10

Это как?

[Мастак]

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

Мастак в сообщении #1525458 писал(а):

есть вершина степени 100

Мастак в сообщении #1525458 писал(а):

степень каждой вершины равна 10

Это как?

У одной вершины степень 100, а у всех остальных - 10.
PS Описка, недописка.

[marie-la]

Рассмотрим граф, из которого удалили вершину степени 100. В полученном графе есть компоненты связности. Рассмотрим одну из них. Поскольку исходный граф связен, данную компоненту соединяет как минимум одно ребро с вершиной степени 100. Если бы такое ребро было только одно, то в компоненте связности все вершины имели бы степень 10, кроме одной со степенью 9. Сумма степеней вершин в компоненте не может быть нечетной. Поэтому ребер, соединяющих данную компоненту с вершиной степени 100, не менее двух. Одно из них можно удалить.

[Мастак]

marie-la в сообщении #1525500 писал(а):

Рассмотрим граф, из которого удалили вершину степени 100. В полученном графе есть компоненты связности. Рассмотрим одну из них. Поскольку исходный граф связен, данную компоненту соединяет как минимум одно ребро с вершиной степени 100. Если бы такое ребро было только одно, то в компоненте связности все вершины имели бы степень 10, кроме одной со степенью 1. Сумма степеней вершин в компоненте не может быть нечетной. Поэтому ребер, соединяющих данную компоненту с вершиной степени 100, не менее двух. Одно из них можно удалить.

Спасибо.
Симпатично коротко. (Моё доказательство длиннее).

PS Исправил по логике.

Продолжение. Дописывание. ... И так удалив 50 ребер, вернем к оставшимся 50 ребрам удаленную вершину, связав через нее в один компонент связности все рассматриваемые условно-разные компоненты связности. Таким образом удалили 50 ребер, не нарушив связности графа.

[marie-la]

Мастак в сообщении #1525705 писал(а):

PS Исправил по логике.

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

[Мастак]

marie-la в сообщении #1525737 писал(а):

Мастак в сообщении #1525705 писал(а):

PS Исправил по логике.

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

Мда, болтающегося ребра без вершины на конце (ребра без двух вершин на концах) не может быть
в понятии "граф". Поэтому я условно дорисовал к болтающемуся ребру виртуальную вершину, а Вы условно вычеркнули из компонента связности другие возможные болтающиеся ребра, кроме одного.