Algoritmo de eliminación inversa

El subgrafo restante (g) generado por el algoritmo no está desconectado, ya que el algoritmo lo verifica en la línea 7. El subgrafo resultante no puede contener un ciclo, puesto que, de ser así, al recorrer las aristas encontraríamos la arista máxima del ciclo y la eliminaríamos. Por lo tanto, g debe ser un árbol generador del grafo principal G.

Demostramos que la siguiente proposición P es verdadera por inducción: Si F es el conjunto de aristas que quedan al final del bucle while , entonces existe algún árbol de expansión mínima que (sus aristas) son un subconjunto de F.

1. Claramente, P se cumple antes del inicio del bucle while. Dado que un grafo conexo ponderado siempre tiene un árbol de expansión mínima y dado que F contiene todas las aristas del grafo, entonces este árbol de expansión mínima debe ser un subconjunto de F.
2. Ahora supongamos que P es verdadera para algún conjunto de aristas no final F y sea T un árbol de expansión mínimo que está contenido en F. Debemos demostrar que después de eliminar la arista e en el algoritmo existe algún (posiblemente otro) árbol de expansión T' que es un subconjunto de F.
   1. Si la siguiente arista eliminada e no pertenece a T, entonces T=T' es un subconjunto de F y se cumple P.
   2. De lo contrario, si e pertenece a T: primero observe que el algoritmo solo elimina las aristas que no causan una desconexión en F. Por lo tanto, e no causa una desconexión. Pero eliminar e causa una desconexión en el árbol T (ya que es un miembro de T). Supongamos que e separa T en subgrafos t1 y t2. Dado que todo el grafo está conectado después de eliminar e, entonces debe existir un camino entre t1 y t2 (distinto de e) por lo que debe existir un ciclo C en F (antes de eliminar e). Ahora debemos tener otra arista en este ciclo (llamémosla f) que no está en T pero sí en F (ya que si todas las aristas del ciclo estuvieran en el árbol T, entonces ya no sería un árbol). Ahora afirmamos que T' = T - e + f es el árbol de expansión mínima que es un subconjunto de F.
   3. Primero demostramos que T' es un árbol de expansión . Sabemos que al eliminar una arista en un árbol y agregar otra que no genere un ciclo, obtenemos otro árbol con los mismos vértices. Dado que T era un árbol de expansión, T' también debe serlo . Esto se debe a que agregar "f" no genera ciclos, ya que se elimina "e" (nótese que el árbol T contiene todos los vértices del grafo).
   4. En segundo lugar, demostramos que T' es un árbol de expansión mínima . Tenemos tres casos para las aristas "e" y "f". wt es la función de peso .
      1. wt( f ) < wt( e ) esto es imposible ya que esto hace que el peso del árbol T' sea estrictamente menor que T . dado que T es el árbol de expansión mínima, esto es simplemente imposible.
      2. wt( f ) > wt( e ) esto también es imposible. ya que entonces cuando recorremos los bordes en orden decreciente de pesos de borde debemos ver " f " primero. como tenemos un ciclo C, eliminar " f " no causaría ninguna desconexión en F. por lo que el algoritmo lo habría eliminado de F antes. por lo tanto, " f " no existe en F lo cual es imposible (hemos demostrado que f existe en el paso 4.
      3. entonces wt(f) = wt(e) por lo que T' también es un árbol de expansión mínima . por lo tanto, nuevamente se cumple P.
3. por lo tanto P se cumple cuando el bucle while termina (que es cuando hemos visto todas las aristas) y demostramos al final que F se convierte en un árbol de expansión y sabemos que F tiene un árbol de expansión mínimo como subconjunto. por lo tanto F debe ser el árbol de expansión mínimo en sí mismo.