Эйлеровы цепи и циклы. Существование эйлерова цикла

Определение 1. Эйлеровой цепью (циклом) называется цепь (цикл), содержащая все ребра графа. Граф, имеющий эйлеров цикл, называется эйлеровым графом.

Теорема 1. Конечный мультиграф G является эйлеровым  1) связен и 2) все его вершины имеют четные степени.

Гамильтоновы цепи (циклы). Существование гамильтонова цикла.

Определение 1. Гамильтоновой цепью (циклом) называется простая цепь (цикл), проходящая через каждую вершину графа. Граф, имеющий гамильтонов цикл называется гамильтоновым.

Остовные подграфы графа G, представляющие собой циклы, т. е. 2-факторы, являются гамильтоновыми циклами.

Легко найти гамильтонов цикл в додекаэдре.

Несмотря на сходство в определении эйлеровых и гамильтоновых циклов, соответствующие теории для этих понятий имеют мало общего. Никакого общего критерия существования гамильтонова цикла неизвестно.