Hola Lorena.
Va bien. Vamos a ver algunos detalles.
"se forma un ciclo, ya que T tenía la mínima cantidad de aristas posibles"
Es cierto que se forma un ciclo. Pero porque tiene la máxima cantidad de aristas posibles para que no haya ciclos.
Va bien. Vamos a ver algunos detalles.
"se forma un ciclo, ya que T tenía la mínima cantidad de aristas posibles"
Es cierto que se forma un ciclo. Pero porque tiene la máxima cantidad de aristas posibles para que no haya ciclos.
Para lo que T tiene la mínima cantidad de aristas es para ser un árbol de cubrimiento.
"el grafo restante queda conexo" ...."volvemos a tener un MST"
Lo que interesa que sea conexo es T', y lo es por el argumento que das. Con eso, y como no tiene ciclos y tiene la misma cantidad de aristas que T, sabemos que es un árbol de cubrimiento. Pero todavía no podemos afirmar que sea un MST, eso es lo que hay que demostrar. Lo que sabemos por ahora es que si es distinto de T, porque emax es distinta de e (si emax fuera e entonces T' sería T), tiene menor costo que T. Pero falta demostrar que T' tiene menor costo que cualquier otro árbol de cubrimiento de G'. Al haber agregado e hay muchos más árboles, que no pertenecían a G.
"no pertenecen a T' => no pertenecen a un MST de G"
En realidad no es cierto, porque si emax es distinta de e, entonces no pertenece a T' pero pertenece a T, que sí es un MST de G.
¿Puede ser que hayas querido poner "=> no pertenecen a un MST de G' "? Eso sí, es lo que hay que demostrar.
Está bien que intentes usar una arista a, genérica que no pertenece a T'. Y es casi correcta la demostración de que T' U {a} no es un MST. Pero no podés usar que T' es un MST, porque eso es lo que querés demostrar. Está bien que uses que T' es un árbol de cubrimiento, que es lo que ya sabés (¿puede ser que estés confundiendo el concepto MST con el de árbol de cubrimiento?). Y de hecho estás demostrando algo más fuerte que T' U {a} no es un MST, estás demostrando que no es un árbol, de cubrimiento o no.
De todas formas, esto no te ayuda a probar que la arista a no pertenece a otro árbol T'', distinto de T', que podría ser el MST.
Clasificá a la arista a en dos casos.
Uno, a es emax. ¿Puede emax pertenecer a un MST? Usá el enunciado 4.20.
Dos, a no es emax, y entonces es una arista de G y no de T, el MST de G. ¿Qué implica el enunciado 4.20 respecto a la arista a y los ciclos de G? ¿Se puede extender esa conclusión a G'?
Pensalo y cualquier duda preguntá de nuevo.