Árvores
Fazer a lista de conexidade será bem proveitoso.
Dizemos que um grafo $T = (V,A)$ é uma floresta se não possui ciclos como subgrafos. Uma floresta conexa é dita ser uma árvore.
1 Observe o grafo cujo conjunto de vértices corresponde aos pontos pretos abaixo e cujas arestas estão todas representadas. Esse grafo é uma floresta? Ele possui uma floresta como subgrafo? Mais do que isso, ele possui uma floresta como subgrafo induzido? Alguma de suas componentes conexas é uma árvore? Se sim, quantas?
2 Mostre que um grafo $G = (V,A)$ é uma floresta se, e somente se, dados $x,y \in V$, existe no máximo um caminho de $G$ ligando $x$ e $y$.
2.1 Conclua que $G = (V,A)$ é uma árvore se, e somente se, dados $x,y \in V$, existe exatamente um caminho de $G$ ligando $x$ e $y$.
Dado $G = (V,A)$ um grafo, considere uma aresta $e \in A$ e tome $C_e$ a componente conexa do grafo que contém as duas extremidades de $e$. Denote por $G[C_e] = (V',E')$ o subgrafo de $G$ induzido a $C_e$. Dizemos que $e$ é uma ponte de $G$ se o grafo $C_e\setminus e : = (V',E'\setminus \{e\})$ é desconexo.
3 Verifique que as arestas do grafo abaixo representadas por linhas tracejadas são pontes.
4 Mostre que um grafo $G$ é uma floresta se, e somente se, todas as suas arestas são pontes. Conclua que um grafo conexo é uma árvore se, e somente se, todas as suas arestas são pontes.
4.1 Seja $G$ um grafo conexo. Mostre que $G$ admite uma árvore como um subgrafo que contém todos os seus vértices. Uma árvore como essa é conhecida como árvore geradora de $G$. Ela é única?
5 Mostre que, se $T$ é uma árvore com $n$ vértices, então $T$ possui $n-1$ arestas.
5.1 Mostre que, se um grafo possui $n$ vértices e $n-1$ arestas, então ele possui ao menos dois vértices de grau $1$.
5.2 Mostre que um grafo conexo com conjunto de vértices finito é uma árvore se, e somente se, possui $n$ vértices e $n-1$ arestas.
