Один из алгоритмов построения графов с заданным количеством вершин нечётной степени — алгоритм Кристофидеса-Сердюкова. 1 Он включает два этапа: 1

1. Вычисление минимального остовного дерева. 1 Нужно связать все вершины графа таким образом, чтобы получилось совокупное минимальное расстояние. 1
2. Определение вершин графа с нечётной степенью соединений. 1 Для этого используют лемму о рукопожатиях, согласно которой любой конечный неориентированный граф имеет чётное число вершин нечётных степеней. 1 Эта закономерность позволяет гарантированно связать все без остатка вершины с нечётной степенью между собой. 1

Также для построения графов с заданным количеством вершин нечётной степени можно использовать алгоритм построения Эйлерова цикла. 2 Он напоминает поиск в глубину, но пройденными помечаются не вершины, а рёбра графа. 2 Чтобы построить Эйлеров путь, нужно запустить алгоритм из вершины с нечётной степенью. 2