Задача про граф

[_mv]

Здравствуйте, уважаемые посетители форума!
Подскажите, пожалуйста, как решить такую задачу:

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

Спасибо.

[Sonic86]

Если я правильно понял, то не очень понятно, зачем число вершин четное.
Покрывающее дерево Вас устроит?

[_mv]

Sonic86
Прошу прощения! Забыл одно слово в задаче!


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


Спасибо.

[hippie]

Красивая задача, хотя и простая!

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

Допустим, что при таком соединении нашлись два маршрута, содержащие общее ребро XY (т.е. присутствуют пути AXYB и CXYD). Тогда можно точки переразбить на пары, так, чтобы в одну пару включить точки, соединённые с концом X ребра XY, а в другую пару включить точки, соединённые с концом Y ребра XY (т.е. образовать пути AXC и BYD). (Остальные пары остаются без изменений.) При этом маршруты, соединяющие новые пары, состоят из тех же рёбер, что и исходные, за исключением двух рёбер XY. Т.е. сумма "длин путей" оказалась на 2 меньше, чем в исходном соединении. А это противоречит минимальности суммы "длин путей" в исходном соединении.

[_mv]

Спасибо! Очень ценные рассуждения!