Árvores

ÁRVORES

Definição
Uma árvore é um grafo conexo sem circuito. Note que como um grafo precisa conter no mínimo um vértice, uma árvore contém no mínimo um vértice. Também temos que uma árvore é um grafo simples, pois laços e arestas paralelas formam circuitos. Um grafo não conexo que não contém circuitos será nomeado floresta. Nesse caso temos um grafo onde cada componente é uma árvore. Propriedades das árvores
Antes de apresentar o primeiro teorema relacionado as árvores, vamos provar o seguinte lema:
Lema 1: Seja C1 e C2 dois caminhos simples distintos entre dois vértices vj e vk de um grafo. A união C1 U C2 contém no mínimo um circuito.
Prova: Como os dois caminhos começam em vj e terminam em vk, e que eles são distintos, existe no mínimo um vértice onde eles se separam e um vértice onde eles se juntam. Seja vm o primeiro vértice onde eles se separam e vn o primeiro vértice onde eles se juntam. Necessariamente, fora vm e vn, não existe nenhum vértice comum entre esse dois caminhos. Podemos então formar um circuito, saindo de vm, indo até vn por um caminho, e voltar a vm pelo outro caminho.
Teorema 1: Existe exatamente um caminho simples entre cada par de vértices de uma árvore T.
Prova: Como T é conexo, existe um caminho entre cada par de vértices. Suponhamos agora que existem dois caminhos distintos entre dois vértices vj e vk. Pelo lema 4-1, já sabemos que isso implica a existência de um circuito, o que é impossível em uma árvore.
Teorema 2: Se existe exatamente um caminho simples entre cada par de vértices de um grafo G,
G é uma árvore.
Prova: Se existe um caminho simples entre cada par de vértice de G, G é conexo. Suponhamos agora que o grafo não é uma árvore. Então, existe no mínimo um circuito. Já sabemos que entre qualquer par de vértices de um circuito, existem dois caminhos distintos, o que contradiz a hipótese.

Teorema 3: Uma árvore que contém n vértices contém exatamente n-1 arestas.
Prova: A prova é por indução. O caso n = 1 é trivial, pois teremos