Comment by PrunJuice

> If the value of the optimal solution has changed it means that the edge must be in the optimal optimization solution.

I interpreted this as meaning you were selecting the falsifying removals' edges, instead of removing the non-falsifying ones. You've got it.