Prove que:
Todo subgrafo conexo de uma árvore também é uma árvore.
Todo subgrafo conexo de uma árvore também é uma árvore.
Passo 1
Beleza, então o exercício pede para provar que todo subgrafo conexo de uma árvore também é uma árvore. Estamos lidando com conceitos de teoria dos grafos, especificamente com árvores e subgrafos. Para resolver isso, vamos precisar entender o que é uma árvore, o que é um subgrafo e o que significa ser conexo.
Passo 2
Vamos começar lembrando o que é uma árvore. Em teoria dos grafos, uma árvore é um grafo que é conexo (ou seja, há um caminho entre qualquer par de vértices) e não possui ciclos (não há ciclos fechados). Outra forma de dizer é que uma árvore com
vértices tem exatamente
arestas.
Passo 3
Agora, vamos entender o que é um subgrafo. Um subgrafo de um grafo
é formado por um subconjunto dos vértices de
e um subconjunto das arestas de
que ligam esses vértices. Quando falamos de um subgrafo conexo, queremos dizer que esse subgrafo também é conexo; ou seja, ainda há um caminho entre qualquer par de vértices dentro dele.
Passo 4
Para provar que todo subgrafo conexo de uma árvore é uma árvore, precisamos verificar duas coisas:
- O subgrafo é conexo.
- O subgrafo não possui ciclos.
Sabemos que o subgrafo em questão já é conexo, conforme o enunciado. Então, precisamos mostrar que ele não tem ciclos.
Passo 5
Vamos assumir, por contradição, que o subgrafo conexo de uma árvore possui um ciclo. Se isso acontecesse, então o ciclo seria um ciclo no próprio grafo árvore original, o que contradiz a definição de árvore (não ter ciclos). Portanto, nossa suposição de que o subgrafo possui um ciclo está errada.
Passo 6
Outra maneira de ver isso é contar as arestas. Se o subgrafo conexo tem
vértices, para ser uma árvore, ele deve ter exatamente
arestas. Como a árvore original tinha
arestas para
vértices e estamos removendo vértices e arestas para formar o subgrafo, o número de arestas no subgrafo será menor ou igual a
, garantindo que não haja ciclos.
Resposta
Portanto, todo subgrafo conexo de uma árvore também é uma árvore.