Эйлеровы и гамильтоновы циклы

Эйлеров цикл содержит не только все ребра (по одному разу), но и все вершины графа (возможно, по несколько раз). Ясно, что эйлеровым может быть только связный граф. С эйлеровым циклом как раз связана задача о кенигсбергских мостах, приведшей к исторически первой попытке развития теории графов как самостоятельного предмета. Чтобы решить данную задачу потребуется сначала сформулировать и доказать теорему. Эта теорема справедлива также и для мультиграфов, и для псевдографов, исключая тот случай, когда псевдограф имеет только одну вершину.