You need to start and end the Euler tour at the ends of the edges you removed.