Теорема 1. Граф является эйлеровым тогда и только тогда, когда нечетную степень имеют не более двух вершин.

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

Пример 1. Закрытое письмо (см. рис. 4.2) невозможно нарисовать не отрывая карандаш и проходя каждую линию ровно один раз, а открытое – можно.

Рис. 4.2. Закрытое письмо и открытое письмо

Отметим две другие задачи: Задача о трех домах и трех колодцах и задача о наследстве. В последней из них требуется разделить плоскую односвязную область на пять односвязных областей, каждая пара которых имеет общую границу ненулевой длины.

Хорошо известна задача о раскраске плоской карты в четыре цвета. Она была решена Аппелем, Рингелем и Янгсом в 1971 году с помощью ЭВМ.