Removing egdes connecting a vertex with vertices of higher (or same) degree

Question

Suppose you have a graph on vertices $v_1, v_2, v_3, …, v_n$.

Now, an operation starts.

Step 1: remove all edges $v_1v_k$ for such k that $deg(v_k) \ge deg(v_1)$

Step 2: remove all edges $v_2 v_k$ for such k that $deg(v_k) \ge deg(v_2)$ (here, $deg(v_i)$ denotes degree of $v_i$ in the graph obtained on step 1, not in the original graph. Also, $v_2v_1=v_1v_2$)

And so on until step n.

Question: Is it true that after such procedure the remaining graph will contain an isolated vertex?

I have no idea how to prove or disprove this, as the procedure is quite complicated. It is obviously true for trees (as they contain a vertex of degree 1) and complete graphs.

False proof: if $deg(v_i) \le deg(v_j)$ in the original graph, the edge $v_iv_j$ will be removed on step i, so all vertices will be isolated.

Why it is false: before we arrive to step i, $deg(v_i)$ and $deg(v_j)$ may change, so the edge may remain.

The idea of using the vertex of minimal degree fails for the same reason: when we consider step corresponding to that vertex, it can already be non-minimal (as a consequence of previous steps)

Any hints are welcome.

By the way, here's a code for Wolfram Mathematica to check this for a random graph with 10 vertices and 40 edges (I didn't find counterexamples, but may be the code is flawed?) [Be wary, if you want to change 10 to something else, it should be done in three places (in the beginning and in the cycles' conditions )] :

g = RandomGraph[{10, 40}, VertexLabels -> Placed[Automatic, Center], VertexSize -> .5];
gg = g

For[i = 1, i < 11, i++, For[j = 1, j < 11, j++, If[i != j  && MemberQ[EdgeList[g], Min[i, j] \[UndirectedEdge] Max[j, i]] && VertexDegree[g, j] >= VertexDegree[g, i], g = EdgeDelete[g, Min[i, j] \[UndirectedEdge] Max[j, i]], ]]]
g

Answer 1

A quick run with Sage found easily some counter-examples for your conjecture, on 10 vertices.

It has degree sequence $[7, 6, 6, 6, 5, 5, 4, 4, 4, 3]$. After applying your algorithm, we end up with

Here is my code for information

def find_counter_test(nb_tries):
    n=10
    p=0.5
    for tries in range(nb_tries):
        G=graphs.RandomGNP(n,p)
        G_init = G.copy()
        for i in range(n):
            di = G.degree(i)
            for j in range(n):
                dj=G.degree(j)
                if dj>=di:
                    G.delete_edge(i,j)
        min_deg=min(G.degree_sequence())            
        if min_deg > 0:
            G_init.show()
            G.show()
            return(G_init)
    return(False)

Here is the full details of the operations,step by step.