===== A ordem dos vértices de um grafo conexo =====

Se $U \subseteq V(G)$ e $G[U]$ é conexo, nós também dizemos que $U$ é conexo (em $G$), onde $G[U]$ é um [[.defsubinduc |subgrafo induzido]] de $G$.

<WRAP round box 80%>
=== Teorema ===
//Os vértices de um grafo [[.defConexo|conexo]] $G$,digamos $v_1, \dots, v_n$, sempre podem ser ordenados tais que $G_i := G[v_1,\dots,v_i]$ seja conexo para todo $i = 1, ..., n$.//
</WRAP>

<WRAP round box 100%>
**Demonstração: ** Tomemos qualquer vértice de $V(G)$, como $v_1$, e vamos supor indutivamente que $v_1, \dots, v_i$ foram escolhidos tais que $i < |G|$. Agora tomemos um vértice $v \in G - G_i$. 

Como $G$ é [[.defConexo|conexo]] ele contém o caminho $v-v_1$. Vamos chamá-lo de $P$. Escolhamos como $v_{i+1}$ o último vértice de $P$ em $G - G_i$, então $v_{i+1}$ possui um [[.vizinhosDeV| vizinho]] em $G_i$. Isso pode ser feito de maneira indutiva para todos $G_i$, resultando na prova do teorema.

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