At this point, we must choose one of the two edges from the right-most end of edge 9. We cannot take the edge going back to the start. While this may not be clear from the original graph, it is clear from the copy . Pick an edge going out from the last visited vertex. Label the corresponding edge from the original graph.
Warnings Make sure to keep start each step from the end of the last chosen edge.
Make sure that you do not disconnect the copy. Make sure to number the chosen edges consecutively. If a vertex has no more edges coming out from it, you may erase it from the copy. Stop When you have erased the entire copy, then you have traced every edge in the graph, and you may stop. By computing the degrees of the vertices in a graph, we can tell whether or not it has an Euler tour .