Чётность графа с помощью циклов можно определить через существование Эйлерова цикла. 14 Такой цикл проходит по одному разу через каждое ребро графа. 1

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

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