Nada se borra: lo único que pasa es que los grados bajan. El número que lleva cada vértice es su grado en lo que queda vivo, y el naranja marca la capa que se está yendo. Siga la ejecución y vea en qué momento un vértice interno se vuelve hoja.
¿Cuántas vueltas del ciclo while va a dar el algoritmo sobre este árbol?
Sin solución aquí. Mire el momento en que un vértice entra a siguiente: siempre es al bajarle el grado a uno, nunca a cero. Explique por qué nunca llega a cero mientras el ciclo siga corriendo. Después cambie mentalmente la línea 13 por if grado[u] <= 1 y diga qué árbol rompería con ese cambio.