Definição: Floresta e Árvore

Classicamente, um grafo acíclico, que não contém nenhum ciclo, é chamado de Floresta. Assim, uma floresta é um grafo que também não possui ciclos como subgrafos, de modo que suas componentes conexas são chamadas Árvores.

Teorema: Equivalências

Seja $T = (V,A)$ um grafo qualquer. Então, as seguintes afirmações são equivalentes:

$(i)$ $T$ é uma árvore.

$(ii)$ Dados $x,y\in V$, existe um único caminho em $T$ que possui $x$ e $y$ como extremidades. Tal caminho é comumente denotado por $xTy$.

$(iii)$ $T$ é minimalmente conexo, isto é, $T$ é conexo mas $T - e$ é um grafo desconexo para toda aresta $e\in A$.

$(iv)$ $T$ é maximalmente acíclico, ou seja, $T$ não possui ciclos como subgrafos, porém, se $x,y \in V$ são vértices não adjacentes, o grafo $T+xy$ admite um ciclo.

Demonstração:

$(i) \Rightarrow (ii)$ Inicialmente suponha que $T=(V,A)$ é uma árvore e fixe $x,y \in V$ quaisquer. Visto que $T$ é um grafo conexo, certamente existe um caminho em $T$ que possui tais vértices como extremidades. Para argumentarmos sua unicidade, suponha que existam caminhos $P$ e $Q$ distintos que possuem $x$ e $y$ como extremidades.

Enumere ainda os vértices de $P$ como $\{p_1,p_2,\dots,p_n\}$ e os vértices de $Q$ como $\{q_1,q_2,\dots,q_m\}$ de modo que $p_1=q_1 = x$, $p_n=q_m = y$ e $p_ip_{i+1},q_jq_{j+1}\in A$ para quaisquer $1 \leq i < n$ e $1 \leq j < m$. Uma vez que $P$ e $Q$ são distintos, deve haver $1 \leq i < \min \{m,n\}$ tal que $p_{i+1}\neq q_{i+1}$. Fixe $i$ mínimo com tal propriedade. Por outro lado, $y = p_n = q_m $ atesta que o conjunto de índices $\{i < j \leq n : p_j \in Q\}$ é não vazio. Ao tomarmos $j$ também como menor elemento desse conjunto, tem-se que $\{p_i,p_{i+1},p_{i+2},\dots,p_{j-1},p_j\}$ e $\{q_i,q_{i+1}, q_{i+2},\dots, q_{k-1},q_k\}$ são conjuntos de vértices de caminhos de $T$ que são disjuntos a menos de seus extremos, se $k \leq m$ é tomado de modo que $p_j = q_k$. Isso, contudo, contradiz o fato de $T$ não possuir um ciclo como subgrafo. Logo, entre $x$ e $y$ deve haver um único caminho em $T$.

$(ii) \Rightarrow (iii)$ Suponha agora que quaisquer dois vértices de $T$ são extremidades de um único caminho em $T$ e fixe $e\in A$ uma aresta qualquer, denotando por $x$ e $y$ suas extremidades. A aresta $e$, portanto, descreve o único caminho em $T$ entre os vértices $x$ e $y$. Logo, no grafo $T\setminus e$ não deve haver um outro caminho que possui esses mesmos vértices como extremidades. Isto é, $T\setminus e$ é um grafo desconexo, verificando a minimalidade de $T$ como grafo conexo.

$(iii) \Rightarrow (iv)$ Suponha agora que $T$ é um grafo minimalmente conexo. Por um momento, suponha que existam $v_1,v_2,\dots,v_n\in V$ vértices que, nessa ordem, configuram um ciclo em $T$. Denote por $e$ a aresta entre os vértices $v_1$ e $v_n$ e fixe $x,y\in V$ quaisquer. Como $T$ é um grafo conexo, existe $u_1,u_2,\dots,u_m \in V$ vértices que, nessa ordem, são um caminho entre $x = u_1$ e $y = u_m$. Se $e \neq u_iu_{i+1}$ para todo $1 \leq i < m$, então $x$ e $y$ são vértices da mesma componente conexa de $T\setminus e$. Caso contrário, para algum $1 \leq i < m$, tem-se que (sem perda de generalidade) $u_i = v_1$ e $u_{i+1} = v_n$. Portanto, em $T\setminus e$, vale que:

• $x$ e $v_1$ pertencem à mesma componente conexa, como atestado pelo caminho formado pelos vértices $u_1,u_2,\dots,u_i$.
• $v_1$ e $v_n$ pertencem à mesma componente conexa, como atestado pelo caminho formado pelos vértices $v_1,v_2,\dots,v_n$.
• $v_n$ e $y$ pertencem à mesma componente conexa, como atestado pelo caminho formado pelos vértices $u_{i+1},u_{i+2},\dots,u_m$.

Portanto, $x$ e $y$ são vértices de uma mesma componente conexa de $T\setminus e$. Ou seja, provamos que o grafo $T\setminus e$ é conexo, contradizendo a minimalidade de $T$. Logo, $T$ não pode conter um ciclo como subgrafo. Além disso, mesmo que $x,y \in V$ sejam vértices não adjacentes em $T$, a conexidade desse grafo nos garante que existe $P$ um caminho em $T$ que possui esses dois vértices como extremos. A adição de uma aresta entre $x$ e $y$ no grafo, consequentemente, torna este caminho um ciclo. Logo, $T$ é um grafo maximalmente acíclico.

$(iv) \Rightarrow (i)$Finalmente, suponha que $T$ é um grafo maximalmente acíclico. Em particular, $T$ é uma floresta, de modo que, para provarmos que essa é uma árvore, resta-nos concluir que $T$ é conexo. Para tanto, sejam $x,y\in V$ quaisquer. Se $xy \in A$, há trivialmente um caminho de $G$ que os possui como extremidades. Se não, o grafo $T+xy$ admite um ciclo $C$ por hipótese. Como $T$ não possui ciclos como subgrafos, podemos tomar $C$ como tendo conjunto de vértices $\{v_1,v_2,v_3,\dots,v_n\}$ conectados nessa ordem e de modo que $v_1 = x$ e $v_2 = y$. Assim, $v_1,v_2,\dots,v_n$ são vértices que, nessa ordem, define um caminho que possui $x$ e $y$ como extremidades. Isso finaliza a verificação de que $T$ é conexo, e portanto, $T$ é uma árvore.

$\square$

Corolário: Ordenação de vértices

Seja $T = (V,A)$ uma árvore. Se $T$ tem $n$ vértices, podemos escrever $V = \{v_1,v_2,\dots,v_n\}$ de modo que, para todo $1 < i \leq n$, $v_i$ tem exatamente um vizinho em $\{v_1,v_2,\dots,v_{i-1}\}$.

Demonstração:

Uma vez que $T$ é conexo, sabemos que é possível escrever $V = \{v_1,v_2,\dots,v_n\}$ de modo que $T[v_1,v_2,\dots,v_i]$ é conexo para todo $1 \leq i \leq n$. Além disso, como $T$ não possui ciclos como subgrafos, $T[v_1,v_2,\dots,v_i]$ também não possui, de modo que essa é também uma árvore para todo $1 \leq i \leq n$. No caso em que $i > 1$, a conexidade de $T[v_1,v_2,\dots,v_i]$ implica que $v_i$ tem um vizinho em $T[v_1,v_2,\dots,v_{i-1}]$. Como esse grafo é também conexo, o item $(iii)$ da caracterização acima, se aplicado à árvore $T[v_1,v_2,\dots,v_i]$, nos garante que $v_i$ não pode ter mais que um vizinho em $T[v_1,v_2,\dots,v_{i-1}]$. Logo, $v_i$ tem exatamente um vizinho em $\{v_1,v_2,\dots,v_{i-1}\}$.

$\square$

Corolário 1

Se $T$ é uma árvore e $G$ é um grafo com $\delta(G) \geq |T|-1$, então $G$ possui $T$ como subgrafo.

Demonstração:

Conforme garantido pelo Corolário acima, é possível escrever $V(T) = \{v_1,v_2,\dots,v_n\}$ de modo que $v_i$ tem exatamente um vizinho em $\{v_1,v_2,\dots,v_{i-1}\}$ para todo $1 < i \leq n$, em que $n = |V(T)|$. Assim, para cada $1 \leq i \leq n$ e cada $2 \leq j \leq n$, escolha $u_i \in V(G)$ e $e_j \in A(G)$ recursivamente como se segue:

• Considere $u_1 \in V(G)$ um vértice qualquer.
• Suponha que, para algum $i > 1$, os vértices $u_1,u_2,\dots,u_{i-1}\in V(G)$ estão definidos. Seja $1 \leq k \leq i-1$ o índice do único vizinho de $v_i$ em $\{v_1,v_2,\dots,v_{i-1}\}$. Como $\delta(G) \geq n-1$ e $u_k$ tem no máximo $i-2 \leq n-2 < n-1$ vizinhos entre os vértices $\{u_1,u_2,\dots,u_{k-1},u_{k+1},\dots,u_n\}$, escolha um vértice qualquer $u\in N(u_k) \setminus \{u_1,u_2,\dots,u_{k-1},u_{k+1},\dots,u_n\}$ e defina $u_i = u$. Considere $e_i$ como a aresta de pontas $u_k$ e $u_i$.

Pela escolha da enumeração $\{v_1,v_2,\dots,v_n\}$, tem-se que o subgrafo de $G$ dado por $(\{u_1,u_2,\dots,u_n\}, \{e_2,e_3,\dots,e_n\})$ é uma cópia de $T$.

$\square$

Corolário 2

Um grafo conexo com $n$ vértices é uma árvore se, e somente se, possui $n-1$ arestas.

Demonstração:

$(\Rightarrow)$ Suponha inicialmente que $G = (V,A)$ é uma árvore de $n$ vértices. Como antes, é então possível escrever $V = \{v_1,v_2,\dots,v_n\}$ de modo que $v_i$ compartilha apenas uma aresta com algum vértice de $\{v_1,v_2,\dots,v_{i-1}\}$ se $1 < i \leq n$. Logo, como toda aresta $v_iv_j$ (com $i < j$) é contabilizada nessa enumeração pelo vizinho de $v_j$ em $\{v_1,v_2,\dots,v_n\}$, calcula-se que $G$ tem $n-1$ arestas.

$(\Leftarrow)$ Reciprocamente, suponha que $G$ é um grafo conexo com $n$ vértices e $n-1$ arestas. Fixe $T$ uma árvore geradora de $G$. Pela definição de conjunto gerador, $T$ também tem $n$ vértices. Logo, pelo que acabamos de provar, $T$ tem $n-1$ arestas. Em outras palavras, todas as arestas de $G$ são também arestas de $T$. Logo, $G$ e $T$ são o mesmo grafo, provando que $G$ é uma árvore.

$\square$