==== Inferência do tamanho de caminhos e/ou de ciclos em grafos a partir de seu grau, quando $\delta(G) \geq 2$ ====

<WRAP round box 80%>
=== Teorema ===
//Considere $G$ um grafo. Se $\delta(G) \geq 2$ (onde $\delta(G)$ é o [[.grauMinimo| grau mínimo]] de $G$). Então://

$(i) G$ //contém um [[.defCaminho|caminho]] de tamanho maior ou igual a $\delta (G)$;//

$(ii) G$ //contém um [[.defCiclo|ciclo]] de tamanho maior ou igual a $\delta (G) + 1$.//
</WRAP>

<WRAP round box 100%>
//**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 [[.defCiclo|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 [[.vizinhosDeV| 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 [[.grauV| 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.

<wrap right>$\square$</wrap>
</WRAP>

----
<WRAP round tip 50%>
=== Veja também: ===

[[.defCaminho|Caminhos]] e [[.defCiclo|Ciclo]] de um grafo.
</WRAP>