Introdução à Teoria dos Grafos – Aula 12 – Criando componentes ao deletar uma aresta

Professor Marcos Paulo Ferreira de Araújo Aula 12 – Criando componentes ao deletar uma aresta Suponha que estamos trabalhando com um grafo conexo e deletamos uma de suas arestas. O novo grafo obtido agora pode não ser mais conexo. Nesta aula provamos formalmente um fato que pode parecer evidente, mas dá algum trabalho para justificar: demonstramos que após deletar a aresta, ou o grafo obtido continua sendo conexo ou então ele possui exatamente duas componentes conexas.