Notice that each edge that we add changes the degree of exactly 2 nodes.

The number of nodes with an odd degree in the original graph should be either 0, 2, or 4. Try to work on each of these cases.