Worst Case running time of the Minimum Vertex Cover Approximation algorithm

Question

Considering this factor $2$ minimum vertex cover approximation algorithm :

Repeat while there is an edge:

Arbitrarily pick an uncovered edge $e=(u,v)$ and add $u$ and $v$ to the solution. Delete $u$ and $v$ from the graph. Finally output the candidate cover.

I want to find the worst case running time of this algorithm. Since in a fully connected graph we have $O(n^2)$ edges, then the loop will run at most $O(n^2)$ times.

Here I am not sure what the maximal number of delete operations could be or perhaps for less than $O(n^2)$ edges being processed in the loop there would be some scenario with a large number of delete operations would contribute to the overall complexity.

I want to say naively that in the worst case you simply multiply the max number of edges possible with the max number of delete operations possible (both $O(n^2))$ giving $O(n^4)$, but this seems wrong.

Any insights appreciated.