Demostrar que todo grafo conexo no dirigido con $|V | > 2$ resulta en un gráfico conectado si dos vértices eliminados..

Question

¿Cómo puedo demostrarlo?

Demostrar que todo grafo conexo no dirigido con $|V | > 2$ tiene al menos dos vértices tales que si se eliminan uno o ambos (junto con sus aristas incidentes) el grafo resultante sigue estando conectado, y describa un algoritmo eficiente para encontrar dos de esos vértices.

Answer 1

Una pista: Encuentre el gráfico conectado de árbol de expansión (utilizando un algoritmo como la búsqueda de amplitud). Considera los puntos finales de un camino más largo en este árbol de expansión.