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, então seja $C$ componente conexa de $G-T$, como $T$ é normal em $G$, $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$). Sendo assim, escolha $x \in N(C)$ folha de $T$ 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.