Proposição

Em uma árvore $T=(V,A)$ com raiz $r$, a relação $\leq$ é uma relação de ordem.

Demonstração: Para que esta proposição seja verdadeira precisamos provar as três propriedades de uma relação de ordem: reflexiva$(i)$, anti-simétrica$(ii)$ e transitiva$(iii)$.

$(i)$ Para todo $x \in V$, tem-de trivialmente que $x \in rTx$, isto é, que $x \leq x$. Portanto, a relação $\leq$ é reflexiva;

$(ii)$ Dado $x\in V$, enumere os vértices de $rTx$ como $\{v_0,v_1,\dots,v_n\}$, com $r = v_0$, $x = v_n$ e de modo que, nessa ordem, esses vértices descrevem $rTx$ como caminho. Se $y\in V$ é tal que $y \leq x$, tem-se então que $y = v_i$ para algum $0 \leq i \leq n$. Com isso, o único caminho entre $r$ e $y$ é dado pelos vértices $v_0,v_1,\dots,v_i \in V$ nessa ordem. Assim, caso $x \leq y$, devemos ter $x = v_j$ para algum $1 \leq j \leq i$. Como $j = n$ (pois $x = v_n$), provamos que $i = n$, de modo que $x = y$. Em suma, verificamos que $x = y$ sempre que $x \leq y$ e $y \leq x$. Portanto, a relação $\leq$ é anti-simétrica;

$(iii)$ Suponha que $x,y,z \in V$ são tais que $x \leq y$ e $y \leq z$. Como antes, enumere os vértices do caminho $rTz$ como $\{v_0,v_1,\dots,v_n\}$ com $v_0 = r$, $v_n = z$ e de modo que, nessa ordem, esses vértices descrevem $rTz$ como caminho. Como $y \in rTz$, tem-se que $y = v_k$ para algum $0 \leq k \leq n$. Assim, $rTy$ é o subcaminho formado pelos vértices $v_0,v_1,v_2,\dots,v_k$. Dado que $x\in rTy$, tem-se que $x = v_i$ para algum $0 \leq i \leq k$. Em particular, $x\in rTz$, provando que $x \leq z$. Portanto, a relação $\leq$ é transitiva.

$\square$

1. A altura de um vértice $x \in V$ é definida como comprimento do caminho $rTx$;
2. Dado $x\in V$, seu fecho para baixo consiste no conjunto de vértices $\lceil x \rceil = \{y \in V : y \leq x\}$, enquanto seu fecho para cima corresponde à coleção $\lfloor x \rfloor = \{y \in V : y \geq x\}$. Essa notação pode ser estendida para coleções de vértices de maneira natural: dado $X\subset V$, denotamos seu fecho para baixo e para cima respectivamente como $\lceil X \rceil = \displaystyle \bigcup_{x \in X} \lceil x \rceil $ e $\lfloor X \rfloor = \displaystyle \bigcup_{x \in X} \lfloor x \rfloor $. Com isso, $X$ é dito ser fechado para baixo se $X = \lceil X \rceil$ e fechado para cima caso $X = \lfloor X \rfloor$. Observamos ainda que, para todo $x\in V$, a ordem $\leq$ em $\lceil x \rceil$ é total, isto é, dados $y,z \in \lceil x \rceil$, tem-se que $y \leq z$ ou $z \leq y$. Afinal, se $v_1,v_2,\dots,v_n \in V$ são vértices que, nessa ordem, descrevem o caminho $rTx$, tem-se que $y = v_i$ e $z = v_j$ para certos $1 \leq i \leq n$. No caso em que $i \leq j$, então, $v_i \in rTv_j$, de onde segue que $y \leq z$. Se $j \leq i$, analogamente, vale que $v_j \in rTv_i$, situação em que $z \leq y$.
3. Se $x$ e $y$ são extremidades de uma aresta $e\in A$, então $x \leq y$ ou $y \leq x$. Afinal, $T\setminus e$ é um grafo desconexo e uma de suas componentes conexas deve conter $r$ e alguma das extremidades de $e$. Se essa componente contém $r$ e $x$, então há um caminho entre esses dois vértices nessa componente. Tal caminho descreve $rTy$ se concatenado com a aresta $e$, de onde concluímos que $x \leq y$. No caso em que $r$ e $y$ estão na mesma componente conexa de $rTx$, tem-se analogamente que $y \leq x$.
4. Por definição, tem-se que $r \in rTx$ para todo $x\in V$, de onde segue que $r \leq x$. Em suma, a raiz é o único elemento minimal da ordem $\leq$ em $T$. Um elemento maximal $v$ dessa ordem, entretanto, deve possuir grau $1$: sua minimalidade nos garante, pela discussão do item anterior, que $N(v) \subset rTv$, de modo que, como $rTv$ é um caminho e $T$ não possui ciclos como subgrafos induzidos, $d(v) = |N(v)| = 1$. De maneira recíproca, todo vértice de grau $1$ distindo de $r$ é um elemento maximal da ordem, pois não pode ser vértice de grau $2$ de nenhum caminho da forma $rTy$ para algum $y\in V$. Assim, as folhas de uma árvore $T = (V,A)$ designam seus elementos maximais, que coincidem exatamente com os vértices de grau $1$ de $T$ que são distintos de sua raiz.