Solución:
Un subgrafo $ H $ de $ G $ se llama INDUCIDO, si para dos vértices cualesquiera $ u, v $ en $ H $, $ u $ y $ v $ son adyacentes en $ H $ si y solo si son adyacentes en $ G $.
En otras palabras, $ H $ tiene las mismas aristas que $ G $ entre los vértices de $ H $.
Un subgrafo general puede tener menos aristas entre los mismos vértices que el original.
Entonces, un subgrafo inducido se puede construir eliminando vértices (y con ellos todos los bordes incidentes), pero no más bordes. Si se eliminan bordes adicionales, el subgrafo no se induce.
Para un gráfico original G (V, E), seleccione el conjunto de nodos V ‘de V. Todos los bordes existentes E’ que se conectan entre los nodos en V ‘deben permanecer.
Este subgrafo G ‘se denomina subgrafo inducido.
Si continúa eliminando algunos bordes de E ‘, entonces G’ sigue siendo un subgrafo de G, pero ya no es un subgrafo inducido de G.