Instead of adding edges in increasing order while avoiding cycles, consider the following Reverse-Delete algorithm: