Prove this algorithm for finding the Eulerian path/cycle in a undirected graph Take a look at the procedure (source: https://cp-algorithms.com/graph/euler_path.html)
procedure FindEulerPath(V):

*

*iterate through all the edges outgoing from vertex V;
remove this edge from the graph,
and call FindEulerPath from the second end of this edge;

*add vertex V to the answer.

Note that before running this algorithm, we first check if either all vertices have an even degree or all except two have an even degree (in the latter case we start in any of them).
I understand the Hierholzer's algorithm (https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_algorithm) but I am not sure about proving this one, though I can sense some connection with the Hierholzer's algorithm, perhaps a similar proof with decomposition into circles could be thought of?
 A: I'll try to sketch an idea on how to prove correctness of that algorithm:
Focusing on the case for the Eulerian path (the cycle case can be solved by removing one edge and treating it as an Eulerian path problem), your input is some connected graph $G$ s.t. all nodes have an even degree except for two nodes $x, y$ which have an odd degree.
Note that $FindEulerPath(v)$ adds a node to the answer without recurring iff the degree of $v$ is zero (and therefore, even).
We start by calling $FindEulerPath$ on either $x$ or $y$ (let us pick $x$ w.l.o.g.) and we can note that the first node which will be added to the solution is going to be $y$. In order to observe so note that every time $FindEulerPath$ is called on a vertex $v \neq y$, the degree of $v$ is odd, this can be shown by induction since $x$ has an odd degree and the recursive procedure removes an edge $x \rightarrow z$ before recurring on $z$, and under hypothesis $z \neq y$ we conclude that $z$ has now an odd degree (since it had an even degree before removing the edge). Moreover, at each recursive call $FindEulerPath(z)$, all nodes have an even degree except for $z$ and $y$. This gives the intuition that $y$ will be the first node to be added to the answer since it is the only node on which the algorithm can call $FindEulerPath$ while having an even degree (which is required to add a node to the answer, since we need degree zero).
Moreover, since the algorithm works essentially as a DFS and the graph is connected, $y$ will be reached at some point.
Now we proceed to show that the second node that will be added to the answer is a neighbour of $y$ (this can be repeated by induction, to show that the answer forms a path). In order to do so, let $z$ be the vertex which we explored right before calling $FindEulerPath(y)$ and note that after calling $FindEulerPath(y)$ and adding $y$ to the answer, the graph is such that all nodes have an even degree (by the previous observation, since only the node on which $FindEulerPath$ is called and $y$ can have an odd degree). Now either $z$ has degree zero, and thus it gets added to the answer, with $z$ being a neighbour of $y$, or it picks some edge $z\rightarrow z'$ and recursively calls $FindEulerPath(z')$ after removing the edge $z\rightarrow z'$. This puts us in the same situation we had at the beginning since $z$ and $z'$ are the only two vertices with an odd degree, and since we called $FindEulerPath$ on $z'$, then $z$ will be the next node to be added to the answer.
This should settle the problem of proving that the answer is a path.
At this point We need to prove that the answer contains every edge exactly once (that is, the answer is Eulerian), and this follows from the fact that every edge is explored at most once, since it gets removed from the graph whenever it is picked, and from the fact that the algorithm works as a DFS, therefore it explores all edges and each time an edge is explored, a recursive call to $FindEulerPath$ occurs, thus there is a 1-to-1 correspondence between edges and procedure calls, and this ensures that when every procedure terminates, and thus adds a new edge to the answer, all edges have been explored and added to the answer.
This is a rough sketch of how I would prove this, some details need to be fixed, but I think it should work. I feel like a more elegant proof can be found using simple cycles, but I'm not an expert in this area and this is what pops in my mind.
Hope this helps!
