after this conversion is performedwe must find path in the graph that visits every edge exactly once if we are to solve the "extra challenge,then we must find cycle that visits every edge exactly once this graph problem was solved in by euler and marked the beginning of graph theory the problem is thus commonly referred to as an euler path (sometimes euler touror euler circuit problemdepending on the specific problem statement the euler tour and euler circuit problemsthough slightly differenthave the same basic solution thuswe will consider the euler circuit problem in this section the first observation that can be made is that an euler circuitwhich must end on its starting vertexis possible only if the graph is connected and each vertex has an even degree (number of edgesthis is becauseon the euler circuita vertex is entered and then left if any vertex has odd degreethen eventually we will reach the point where only one edge into is unvisitedand taking it will strand us at if exactly two vertices have odd degreean euler tourwhich must visit every edge but need not return to its starting vertexis still possible if we start at one of the odd-degree vertices and finish at the other if more than two vertices have odd degreethen an euler tour is not possible the observations of the preceding paragraph provide us with necessary condition for the existence of an euler circuit it does nothowevertell us that all connected graphs that satisfy this property must have an euler circuitnor does it give us guidance on how to find one it turns out that the necessary condition is also sufficient that isany connected graphall of whose vertices have even degreemust have an euler circuit furthermorea circuit can be found in linear time we can assume that we know that an euler circuit existssince we can test the necessary and sufficient condition in linear time then the basic algorithm is to perform depth-first search there are surprisingly large number of "obvioussolutions that do not work some of these are presented in the exercises the main problem is that we might visit portion of the graph and return to the starting point prematurely if all the edges coming out of the start vertex have been used upthen part of the graph is untraversed the easiest way to fix this is to find the first vertex on this path that has an untraversed edge and perform another depth-first search this will give another circuitwhich can be spliced into the original this is continued until all edges have been traversed as an exampleconsider the graph in figure it is easily seen that this graph has an euler circuit suppose we start at vertex and traverse the circuit then we are stuckand most of the graph is still untraversed the situation is shown in figure we then continue from vertex which still has unexplored edges depth-first search might come up with the path if we splice this path into the previous path of then we get new path of the graph that remains after this is shown in figure notice that in this graphall the vertices must have even degreeso we are guaranteed to find cycle to add the remaining graph might not be connectedbut this is not important the next vertex on the path that has untraversed edges is vertex possible circuit would then be when spliced inthis gives the path the graph that remains is in figure on this paththe next vertex with an untraversed edge is and the algorithm finds the circuit when this is added to the