(1.0) Seja G um grafo conexo. Mostre que se toda aresta de G é ponte então G é uma árvore.

Para mostrar que se todas as arestas de um grafo G são pontes, então G é uma árvore, podemos utilizar o seguinte raciocínio: Primeiro, vamos relembrar as definições de grafo conexo, ponte e árvore: - Um grafo é conexo se existe um caminho entre qualquer par de vértices. - Uma aresta é uma ponte se sua remoção aumenta o número de componentes conexas do grafo. - Uma árvore é um grafo conexo sem ciclos. Agora, vamos à demonstração: Suponha que todas as arestas de G sejam pontes. Se G não fosse uma árvore, então teria pelo menos um ciclo. Seja C um ciclo em G. Considere uma aresta e em C. Se removêssemos a aresta e, o grafo G seria dividido em duas ou mais componentes conexas, pois a remoção de uma aresta de um ciclo sempre aumenta o número de componentes conexas. No entanto, isso contradiz a hipótese de que todas as arestas de G são pontes, pois a remoção de qualquer aresta deveria aumentar o número de componentes conexas. Portanto, concluímos que se todas as arestas de G são pontes, então G não pode ter ciclos, o que implica que G é uma árvore. Espero que isso tenha ficado claro! Se tiver mais alguma dúvida, é só perguntar.