# Understanding the correctness of the Euler Tour Technique

I can't prove the correctness of the following algorithm by R. E. Tarjan amd U. Vishkin, as described on wikipedia:

Given an undirected tree presented as a set of edges, the Euler tour representation (ETR) can be constructed in parallel as follows:

We construct a symmetric list of directed edges:

• For each undirected edge $\{u,v\}$ in the tree, insert $(u,v)$ and $(v,u)$ in the edge list.

• Sort the edge list lexicographically. (Here we assume that the nodes of the tree are ordered, and that the root is the first element in this order.)

• Construct adjacency lists for each node (called ''next'') and a map from nodes to the first entries of the adjacency lists (called ''first''):

• For each edge $(u,v)$ in the list, do in parallel:

• If the previous edge $(x,y)$ has $x \neq u$, i.e. starts from a different node, set $first(u)=(u,v)$

• Else if $x \neq u$, i.e. starts from the same node, set $next(x,y) = (u,v)$

Construct an edge list (called $succ$) in Euler tour order by setting pointers $succ(u,v)$ for all edges $(u,v)$ in parallel according to the following rule:

$\mathrm{succ}(u,v)=\begin{cases} \mathrm{next}(v,u) & \mathrm{next}(v,u)\neq \mathrm{nil} \\ \mathrm{first}(v)&\text{otherwise}. \end{cases}$

Why the edge list constructed in the last step is an Euler tour? What theorem or lemma gurantees that every single edge is visited?