The following argument $($which$,$ embarassingly, was lectured alongside the correct proof$)$ contains a

mistake. Find and explain the mistake. It will likely help you to try the argument on some example sets

of arrival words.

Claim: Given a set of arrival words, if the first arrival graph with respect to $v$ is a tree rooted at $v,$ and

the length of the arrival word at $u$ equals the number of times $u$ appears in other arrival words, then

the arrival words arose from an Eulerian circuit.

Proof $($not really$).$ Suppose we start to run the algorithm from $v$ and then get stuck without having

used up every edge.

If we are stuck at $uv,$ then, since the algorithm uses up departures and arrivals in pairs, there must

be more $u$ s in other arrival words than there are letters in the arrival word of $u,$ a contradiction. So$,$ the

only place we can get stuck is $v.$

Suppose we have not yet used up the entirety of the arrival word at $w.$ Since the number of arrivals at

$w$ equals the number of departures, and the algorithm uses them in pairs, we also have not used up a

departure from $w,$ to $w^{\text{'}},$ say. In particular, we have not used up the first arrival at $w^{\text{'}}.$ So$,$ we have not

used a departure from $w^{\text{'}},$ to $w^{\text{'}\text{'}},$ say. So$,$ in particular we have not used the first arrival at $w^{\text{'}\text{'}},$ and so

on$.$

Since the first arrival graph contains no cycles, we cannot get repeat vertices, and must eventually hit

$v,$ so the algorithm wasn't stuck after all.