Question

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

Answer 1

Это неверно.

Строим 2 графа - обычные треугольники. Потом берем, и соиденяем эти 2 треугольника одной вершиной.

Получм что-то похожее, на бабочку для костюма.

Выйдет 4 вершины со степенью 2 и вершину, которая является соединением треугольников, у которой степень 4. Убирая ее получим несвязный граф, состоящий из двух одинаковых частей: 2 соединенные вершины

Answer 2

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

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

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

Теперь давайте рассмотрим два случая:

1. Удаленная вершина не была частью эйлерова цикла: Если удаляемая вершина не принадлежала эйлерову циклу, то граф все равно будет содержать эйлеров цикл, который будет проходить через все оставшиеся вершины. В этом случае граф останется связным.

2. Удаленная вершина была частью эйлерова цикла: Если удаляемая вершина была частью эйлерова цикла, то после её удаления граф разделится на два или более отдельных эйлеровых цикла (подграфы). Однако, так как каждая вершина имеет четную степень, то мы можем объединить эти эйлеровы циклы, добавив одно ребро между двумя вершинами, которые ранее принадлежали различным циклам. После объединения этих циклов получим связный граф.

Таким образом, в обоих случаях после удаления одной вершины граф остается связным.