Подвешивание, ранжирование, упорядочивание в графах

Связный граф, в котором нет циклов, — это дерево. Покажем по индукции, что в дереве с вершиной рёбра можно разбить на пары способом из условия. База очевидна. Теперь пусть любое дерево на вершине можно так разбить. Покажем, что и дерево на вершине тоже можно разбить. Подвесим граф за вершину Для каждой вершины определим её глубину — наименьшую длину пути до этой вершины из Пусть — вершина наибольшей глубины. Тогда — висячая вершина, поскольку иначе мы можем пойти ещё ниже. Пусть соединена с Допустим, из вниз идёт ещё какое-то ребро в вершину Заметим, что также вершина наибольшей глубины, поэтому она также висячая. Давайте удалим вершины и , а как пару рёбер возьмём и Тогда граф остался связным, и можно применить предположение индукции. Если же из вниз ребро идёт только в то удалим вершины и а в качестве ребёр возьмём рёбра из Граф снова останется связным, по индукции искомое разбиение существует, что и требовалось доказать.