Для решения задач по обводке графов без пересечения линий можно использовать метод раскрашивания и разъединения пересекающихся линий. 1

Порядок действий: 1

1. Раскрасить фигуру так, чтобы её граничащие части оказались разного цвета. 1
2. Разъединить пересекающиеся линии таким образом, чтобы закрашенная часть представляла из себя единый кусок. 1
3. Обвести по краю одним росчерком закрашенную область — это и будет искомая линия. 1

Также для решения подобных задач используют правила, связанные с понятиями эйлерова пути и эйлерова цикла: 2

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