Lema

Seja $T$ uma árvore normal em $G$. Temos:

$(i)$ Quaisquer dois vértices $x,y \in T$ são separados em $G$ pelo conjunto $\lceil x\rceil\cap \lceil y\rceil$;

$(ii)$ Se $S \subseteq V(T) = V(G)$, ou seja, se $T$ é árvore geradora de $G$, e $S$ é fechado para baixo , então as componentes conexas de $G-S$ são geradas pelos conjuntos $\lfloor x\rfloor$ com $x$ minimal em $T-S$. Isto é, todo $C$ componente conexa de $G-S$ satisfaz $V(C)=\lfloor x\rfloor$ com $x$ minimal em $C$.

Demonstração:

$(i)$ Seja $P$ um caminho qualquer de $x$ a $y$ em $G$, vamos mostrar que $P$ passa por $\lceil x\rceil \cap \lceil y\rceil$. Se $x$ é comparável a $y$, acabamos, pois $y \in \lceil x\rceil$ ou $x \in \lceil y\rceil$.

Caso contrário, seja $t_1,\ldots,t_n$ uma sequência minimal de vértices em $P\cap T$ tais que $t_1=x$ e $t_n = y$ satisfazendo $t_i$ comparável a $t_{i+1}$ para todo $i$ na ordem de $T$. (Esta sequêcia existe, haja vista que o conjunto de todos os vértices em $P \cap T$,em sua ordem natural conforme ocorrem em $P$, tem esta propriedade porque $T$ é normal e todo segmento $t_iPt_{i+1}$ está contido em $T$ ou é em um $T$-caminho)

(Note ainda que cada $t_i$, que não seja $x$ ou $y$, está na “bifurcação” dos “ramos” visto que para ir de um “ramo” para outro por vértices satisfazendo $t_i$ comparável a $t_{i+1}, \forall i$, se faz necessário passar por estas “bifurcações”.)

Observe, por sua vez, que em nossa sequência mínima não podemos ter $t_{i-1}<t_i>t_{i+1}$, para qualquer $i$, pois teríamos a existência de $rTt_{i-1}Tt_i$ e de $rTt_{i+1}Tt_i$, mas como $rTt_i$ há de ser um caminho único, ou $\exists rTt_{i-1}Tt_{i+1}$ ou $\exists rTt_{i+1}Tt_{i-1}$, de qualquer maneira, $t_{i-1}$ é comparável com $t_{i+1}$, o que faz $t_i$ ser desnecessário, contrariando a proposição da sequência ser minimal.

Tem-se, portanto:

$$x=t_1>\ldots>t_k<\ldots<t_n=y$$

Para algum $k \in \{1,\ldots,n\}$. Como $t_k \in \lceil x\rceil \cap \lceil y\rceil \cap V(P)$ , a prova segue.

$(ii)$ Seja $C$ uma componente conexa de $G-S$, e seja $x$ um elemento minimal de $V(C)$. Note que $V(C)$ não possui outro elemento minimal, pois se este fosse o caso e $x'$ também fosse minimal, teríamos $x$ e $x'$ incomparáveis e portanto ligados por um elemento $y$ tal que $y<x$ e $y<x'$, com $y\in S$ (já que são minimais), porém, como $C$ é conexo, existe um caminho $x-x'$ em $C$. Note que por $T$ ser árvore normal em $G$ isto gera uma contradição, pois ou há um ciclo em $T$, ou um $T$-caminho ligando elementos incomparáveis.

Portanto, como todo vértice de $C$ está acima de algum elemento mínimo de $V(C)$, ele está acima de $x$. Em outras palavras, todo elemento de $C$ é comparável a $x$, já que $T$ é árvore geradora de $G$. Por outro lado, todo vértice $y \in \lfloor x \rfloor$ está em $C$, pois como $S$ é fechado para baixo, o caminho ascendente está em $xTy$ está em $T-S$. Assim, $V(C) = \lfloor x \rfloor$.

Mostremos agora que $x$ é minimal não somente em $V(C)$, mas também em $T-S$. De fato isso acontece,pois os vértices abaixo de $x$ formam uma cadeia $\lceil t \rceil$ em $T$.

Como $t$ é vizinho de $x$,a maximalidade de $C$ como uma componente conexa de $G-S$ implica que $t \in S$ e $t \notin \lfloor x \rfloor$,nos dando $\lceil t \rceil \subseteq S$, desde que $S$ seja fechado para baixo. Isso completa a prova de que cada componente de $G-S$ é gerado por um conjunto $\lfloor x \rfloor$ com $x$ minimal em $T-S$.

Reciprocamente, se $x$ é qualquer elemento minimal de $T-S$, ele também é claramente minimal na componente conexa $C$ de $G-S$ à qual pertence. Então, $V(C) \in \lfloor x \rfloor$ como antes, isto é, $\lfloor x \rfloor = C$.

$\square$

Proposição

Todo grafo conexo contém uma árvore geradora normal com qualquer um de seus vértices como raiz.

Demonstração:

Seja $G$ um grafo conexo e $r \in G$ um seu vértice qualquer. Seja $T$ a árvore maximal normal com raiz em $r$, vamos mostrar que $V(T)=V(G)$.

Suponha que não, e seja $C$ um componente de $G-T$. Como $T$ é normal, $N(C)$ é uma cadeia em $T$(se não fosse e existissem vértices incomparáveis em $N(C)$ existiria um $T$-caminho ligando-os por $C$). Seja, então, $x \in N(C)$ uma folha de $T$, isto é, seu maior elemento, e $y \in C$ adjacente a $x$. Mostraremos que $T':=T \cup \{y\}$ (com a aresta $x-y$) com raiz em $r$ é também árvore normal em $G$.

Seja $P$ um $T'$-caminho em $G$. Se as extremidades de $P$ estão em $T$, então $P$ é um $T$-caminho e como $T$ é normal em $G$ as extremidades são comparáveis. Se não, uma das extremidades é $y$. Suponhamos que $P$ ligue $y$ a um elemento $z \in T \subset T'$ incomparável a $y$, então existiria $T$-caminho $P'$ tal que $zP'yP'x$, contradição! Portanto $T'$ é normal em $G$, contrariando $T$ maximal e terminamos.

$\square$