Доказательство. Сначала доказывается, что существование содержащего все ребра замкнутого пути без кратных ребер равносильно четности всех вершин. Если граф эйлеров, то добавим ребро, соединяющее первую и последнюю вершину эйлерового пути. Получим, что все вершины дополненного графа имеют четные степени.
Пример 1. Закрытое письмо (см. рис. 4.2) невозможно нарисовать не отрывая карандаш и проходя каждую линию ровно один раз, а открытое – можно.
Рис. 4.2. Закрытое письмо и открытое письмо
Отметим две другие задачи: Задача о трех домах и трех колодцах и задача о наследстве. В последней из них требуется разделить плоскую односвязную область на пять односвязных областей, каждая пара которых имеет общую границу ненулевой длины.
Хорошо известна задача о раскраске плоской карты в четыре цвета. Она была решена Аппелем, Рингелем и Янгсом в 1971 году с помощью ЭВМ.