Для решения задач на обходы графов в математике можно использовать следующие утверждения: 1

1. Если в графе больше двух нечётных вершин, то его правильный обход (то есть обход, при котором каждое ребро проходится ровно один раз) невозможен. 1
2. Для всякого чётного связного графа существует правильный обход, который можно начать с любой вершины. 1 Он обязательно кончается в той же вершине, с которой начался. 1
3. Если в связном графе ровно две нечётные вершины, то существует правильный обход, причём в одной из них он начинается, а в другой — кончается. 1
4. В любом графе количество нечётных вершин чётно. 1

Также для решения задач на обходы графов можно использовать алгоритмы поиска в глубину: 5

1. Все вершины графа отмечаются как непосещённые. 5 Выбирается первая вершина и помечается как посещённая. 5
2. Для последней помеченной как посещённой вершины выбирается смежная вершина, которая первая помеченная как непосещённая, и ей присваивается значение посещённой. 5 Если таких вершин нет, то берётся предыдущая помеченная вершина. 5
3. Повторяется шаг 2 до тех пор, пока все вершины не будут помечены как посещённые. 5

Ещё один способ обхода графа — обход в ширину. 5 Основное его отличие в том, что сначала исследуются смежные вершины, а уже потом вершины на следующем уровне. 5