Aqui, iremos apresentar duas demonstrações. A primeira dela será via Lema de Zorn:

Dado $G$ conexo, consideremos a coleção de todas as árvores contidas em $G$ ordenada pela ordem de ser subgrafo (uma ordem parcial). Como $G$ é conexo, qualquer árvore maximal contém todos os vértices de $G$ e, portanto, é uma árvore geradora. Logo, basta mostrar que existe uma árvore maximal. Para isso, precisamos mostrar que cada cadeia possui cota superior, de forma que, pelo Lema de Zorn, existe árvore maximal.

Dada uma cadeia $\mathcal{C}$, vamos mostrar que existe uma árvore $T* \subset G$ que contém todas as árvores de $\mathcal{C}$ como subgrafo. Vamos mostrar que $T* = \cup \mathcal{C}$ satisfaz essa hipótese.

Primeiro, vamos mostrar que $T*$ é conexo. Seja $u, v \in V(T*)$. Então em $\mathcal{C}$ existem duas árvore $T_{u}$ e $T_{v}$ tal que $u \in T_{u}$ e $v \in T_{v}$. Como ambas estão em uma mesma cadeira, são comparáveis. Vamos supor, sem perda de generalidade, que $T_{u} \subset T_{v}$. Então $T_{v}$ contém um caminho que conecta $u$ e $v$, e esse caminho está contido em $T*$.

Agora, basta mostrar que $T*$ é acíclico. Vamos supor que existe $C \subset T*$ ciclo. Cada aresta de $C$ está em uma árvore de $\mathcal{C}$. Essas árvores formam uma subcadeia finita de $\mathcal{C}$, que tem elemento maximal $T$. Então $C \subset T$, o que é uma contradição.

Faremos uma segunda demonstração via indução transfinita.

Seja $G$ conexo. Iremos definir as árvores $T_{\alpha} \subset G$ recursivamente de forma que $T_{\beta} \subset T_{\alpha}$ para todo $\beta < \alpha$. Seja $T_{0}$ um único vértice. Dado $\alpha > 0$ ordinal limite, definiremos $T_{\alpha} = \underset{\beta < \alpha}{\cup} T_{\beta}$. Note que $T_{\alpha}$ é árvore e que “$T_{\beta} \subset T_{\alpha}$ para todo $\beta < \alpha$” também vale para ordinais limite.

Dado um sucessor $\alpha = \beta + 1$, devemos primeiro checar se $G - T_{\beta} = \emptyset$. Se sim, $T_{\beta}$ é uma árvore geradora e terminamos nossa recursão. Caso contrário, $G - T_{\beta}$ tem um vértice $v_{\alpha}$ que é extremidade de uma aresta $e_{\alpha}$ cuja outra extremidade está em $T_{\beta}$. Então a árvore $T_{\alpha}$ obtida da união de $T_{\beta}$ com $v_{\alpha}$ e $e_{\alpha}$ satisfaz a ordem de inclusão.