Si el grafo es plano entonces el grafo recubridor es él mismo, si no, entonces, como K5 y K33 pueden ser recubiertos por un ciclo y un camino simple, un grafo recubridor sería el grafo original cambiando los grafos homeomorfos a K5 y K33 por los caminos planos.
Había pensado en hacerlo por lo de los árboles recubridores pero me pareció muy fácil hacerlo así...
Se puede hace así, pero no alcanza con un paso, porque el grafo puede tener muchos K5s y K33, entonces vas cubriendo cada K5 y K33 por un ciclo cada vez.
Es como un algoritmo:
mientras G no sea plano, encontrar un K5 o un K33 y sustituirlo por un ciclo que lo recorre.
Como en cada paso disminuye la cantidad de aristas, el algoritmo termina, pero si termina es porque encontró un grafo plano.
es más fácil, me parece, encontrar el árbol recubridor, pues es lo mismo, pero en lugar de K5 y K33, es considerar un ciclo.
Saludos