Путь (цикл) в графе называется Эйлеровым, если он проходит по всем рёбрам графа.
Если граф обладает эйлеровым циклом, этот цикл проходит через каждое ребро только один раз, то сам граф является эйлеровым.
Если граф обладает Эйлеровым путем, то он называется полуэйлеровым графом.
Примеры:
Теорема 10. (Эйлер, 1736 г.):
Связный граф является эйлеровым тогда и только тогда, когда все его вершины четны. (Необходимость легко доказывается, т.к. проходя через вершину один раз, мы в неё входим и из неё выходим, т.е. увеличиваем её четность на 2)
Теорема 11:
