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 subgrafo induzido de $G$.
Teorema
Os vértices de um grafo 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$.
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$ é 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 vizinho em $G_i$. Isso pode ser feito de maneira indutiva para todos $G_i$, resultando na prova do teorema.
$\square$