Prove que:
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:
  1. O subgrafo é conexo.
  2. 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.

Exercícios relacionados