Задача со связным графом

[netang]

Цитата:

В связном графе отметили $2n$ вершин. Докажите, что их можно разбить на пары и соединить непересекающимися по ребрам путями.

Выделим из исходного графа связный граф, такой, что из одной вершины исходит только два ребра. Кстати, как такой граф называется? После чего пронумеруем вершины. Возьмём минимальный номер вершины, который соответствует одной из отмеченных $2n$ вершин. Начиная с него и до максимального номера вершины, который соответствует одной из отмеченных $2n$ вершин, выделим $n$ пар непересекающихся между собой по ребрам вершин. Так можно доказать?

(Оффтоп)

Тема с такой задачей уже была [http://dxdy.ru/topic58224.html], но я не хотел подсматривать.

[iancaple]

netang в сообщении #1036612 писал(а):

Выделим из исходного графа связный граф, такой, что из одной вершины исходит только два ребра. Кстати, как такой граф называется?

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

[netang]

Спасибо, что ответили!
Попытка номер 2.

1. Связный граф всегда можно "расчесать", и получить граф в виде дерева (рис. 1).
2. Если на концах такого дерева имеются отмеченные точки, то возникает два варианта:

1. Таких точек чётное количество на одной макушке.
2. Таких точек нечётное количество на одной макушке.

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

Извините за косноязычность. С теорией графов почти не знаком.

[Null]

Тут работает метод крайнего.