Количество росчерков. 
Геометрическая теория графов

Из теорем 6 и 7 следует, что для изображения графа, имеющего не более двух нечетных вершин, достаточно одного росчерка. Подсчитаем количество росчерков, необходимых для изображения графа, содержащего более двух вершин нечетной степени.

Теорема 8. Для связного графа, имеющего нечетные вершины, необходимое количество росчерков равно половине количества нечетных вершин.

Доказательство. Предположим, что связный граф G имеет 2п нечетных вершин (по теореме 1 это количество всегда четно). Зафиксируем две нечетные вершины А и В, а остальные нечетные вершины разобьем на пары. В результате получим (п-1) пар. Соединив вершины в этих парах новыми ребрами, получим сверхграф G] исходного графа, который имеет на п-1 ребер больше, чем исходный граф. Так как связный граф G; имеет ровно две нечетные вершины А и В, то он рисуется одним росчерком, причем начало и конец уникурсальной цепи находятся в точках А и В. Если теперь вернуться к графу G, удалив п-1 ребер, то нам придется «разорвать» уникурсальную цепь п-1 раз. Итак, при изображении графа G необходимо оторвать карандаш п-1 раз, т. е. необходимо ровно и росчерков.