Некоторые графы можно обойти одним контуром, потому что в них есть гамильтоновские контуры или эйлеровы пути, которые включают все вершины или рёбра графа по одному разу. 5

Гамильтонов граф — это граф, в котором можно обойти все вершины, побывав в них по одному разу. 5 Если обход заканчивается в той же вершине, в которой начинался, то в результате получится гамильтонов цикл. 5 Если обход графа закончится в другой вершине, то получится гамильтонова цепь. 5

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

Признаком возможности построения эйлерова цикла в неорграфе является чётность степеней вершин графа. 5 В орграфе полустепени захода и исхода должны быть равны в каждой вершине. 5 Признаком возможности построения эйлеровой цепи в неорграфе является наличие только двух вершин с нечётными степенями, а в орграфе — наличие только двух вершин с разницей входящих и выходящих дуг, равной 1, причём в одной вершине должно быть больше выходящих дуг, а в другой — входящих. 5