графы - Связный граф с 2n нечетными вершинами

Разобьём все вершины графа на пары произвольным образом. Для $%i$%-й пары вершин добавим к графу новое ребро, соединяющие эти вершины. После этого получится связный граф, в котором все вершины имеют чётную валентность. Это значит, что в нём имеется эйлеров цикл. Его можно начать рисовать с любого ребра. Выберем какое-то из добавленных рёбер, и начнём рисовать граф с него. Этому соответствует процесс рисования исходного графа, если добавленные рёбра проводить "в воздухе". Отрывать карандаш от бумаги придётся $%n-1$% раз, потому что первое из добавленных рёбер мы проводим в самом начале, и этому ничего не соответствует. А для каждого из остальных дополнительных рёбер придётся отрывать карандаш от бумаги. Здесь надо заметить, что у нас был эйлеров цикл, и мы возвращаемся в исходную вершину. Это делается уже по "настоящим" рёбрам, то есть не по добавленным. И тогда ровно $%n-1$% добавленное ребро будет соответствовать отрыву карандаша от бумаги.