Teorema

Um grafo conexo $G$ admite um circuito euleriano se, e somente se, todos os seus vértices tem grau par.

Demonstração:

$(\Rightarrow)$ Seja $C$ um circuito euleriano de $G$. Cada vez que um vértice $v$ ocorre no ciclo $C$, há uma contribuição de duas unidades para o grau de $v$, uma aresta para chegar a $v$ e outra para sair. Isto vale não só para os vértices intermediários como também para o vértice final, uma vez que se trata de um ciclo, logo “saímos” e entramos“ no mesmo vértice no início e no final do trajeto.

Como $C$ é um circuito euleriano, cada aresta ocorre exatamente uma única vez em $C$, portanto cada vértice possui grau par.

$(\Leftarrow)$ Seja $G$ um grafo conexo com apenas vértices de grau par. Seja $W = (v_0, a_0,\cdots , a_{t-1}, v_t)$ o caminho mais longo em $G$.

Como $W$ não pode ser aumentado, contém todas as arestas que incidem em $v_t$. Por hipótese, a quantidade dessas arestas é par. Disso $v_0 = v_t$ e $W$ é um ciclo.

Suponhamos então que $W$ não seja euleriano. Então existe uma aresta $a = vv_i \not\in W$ com $v_i\in W$. Logo, existe um caminho $(v, a, v_i, \cdots, a_{t-1}, v_t, a_0, \cdots, a_{i-1}, v_i)$ mais longo do que $W$, o que configura uma contradição à escolha do caminho $W$.

$\square$