Граф, в котором можно обойти все вершины и при этом пройти одно ребро только один раз, каждая вершина должна иметь только чётное число рёбер.

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