Teorema

Considere $G$ um grafo. Se $\delta(G) \geq 2$ (onde $\delta(G)$ é o grau mínimo de $G$). Então:

$(i) G$ contém um caminho de tamanho maior ou igual a $\delta (G)$;

$(ii) G$ contém um ciclo de tamanho maior ou igual a $\delta (G) + 1$.

Demonstração:

Queremos mostrar dois resultados com este Teorema. O primeiro $(i)$ resultado nos diz que o grafo $G$ contém um caminho de tamanho maior ou igual a $\delta (G)$; e o segundo $(ii)$, que o grafo $G$ contém um ciclo de tamanho maior ou igual a $\delta (G) + 1$.

$(i)$ Seja $P = (v_0, \cdots, v_m)$ um caminho maximal de $G$, ou seja, um caminho mais longo de $G$. Então, todos os vizinhos de $v_m$ pertencem ao conjunto de vértices de $P$, caso contrário teríamos um caminho mais longo do que $P$, contrariando a escolha de $P$.

Como $v_m$ está ligado somente a pontos do caminho $P$, o tamanho deste deve ser, no mínimo, o grau de $v_m$. Desse fato temos que $$m \geq d(v_m) \geq \delta(G)$$ Logo, $$m \geq \delta(G)$$ Segue a prova do primeiro resultado, pois.

$(ii)$ Consideremos, agora o menor índice de $i$ tal que $v_iv_m \in A(G)$, ou seja, $v_i$ é vizinho de $v_m$. Então, $C = (v_i,v_{i+1}, \cdots, v_m)$ é um circuito, ou ciclo, de comprimento maior ou igual a $\delta(G) + 1$. Segue assim a prova do segundo resultado.

$\square$