Некоторые графы не могут быть эйлеровыми по следующим причинам:

• Наличие вершин с нечётной степенью. 15 Если в графе есть хоть одна такая вершина, то у него не может быть эйлеровой схемы. 1 Это связано с тем, что при обходе графа с вершинами с нечётной степенью по крайней мере одно ребро, инцидентное такой вершине, придётся обходить повторно. 5
• Наличие более одной компоненты связности с рёбрами. 2 В таком случае нельзя пройти по их рёбрам одним путём. 2

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