Деревья и остовные деревья

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