Dado un grafo conexo no dirigido $G=(V, E)$ . Encuentra el subgrafo inducido $G[W]$ de $G$ con el mayor diámetro $d$ donde el diámetro es la mayor distancia entre cualquier par de vértices.
El diámetro del siguiente gráfico es 2, porque podemos ir de cada nodo a cada uno de los otros nodos a través de un máximo de 2 aristas. Sin embargo, al eliminar un nodo, por ejemplo C (y sus aristas adyacentes), el diámetro aumenta a 3, porque necesitamos 3 aristas de A a E.
Una posible solución sería generar todos los subgráficos, calcular el diámetro y seleccionar el mayor. Sin embargo, el número de subgrafos aumenta exponencialmente con el número de vértices, por lo que es inviable.
