Problem C3 from IMO13 shortlist (AoPS link):

Given an undirected graph. You can perform these 2 operations, one at a time:

1. Remove a vertex with odd degree.

2. Double the graph: for each u, create a copy u'; create edge (u', v') if there is edge (u, v); create edge (u, u') for all u.

Prove that there exists a sequence of these 2 operations such that after performing it, the graph will have no edge.

There's this greedy solution that seems to work really well, that is to remove the odd vertex with largest degree until there's no more odd vertices, then double the graph, then do the same over and over again.

It seems to work for all graphs with <= 7 vertices and for random large graphs. Moreover, the number of operations needed doesn't exceed 3N for all graphs I tested on.

Is it possible to prove that it will work for all graphs? And if it does, what is the upper bound of the number of operations?

Thank in advance.