In my lectures, we proved the following theorem:
A graph $G$ has an Euler trail iff all but at most two vertices have odd degree, and there is only one non-trivial component.
Moreover, if there are two vertices of odd degree, these are the end vertices of the trail. Otherwise, the trail is a circuit.
I am struggling with a small point in the $\leftarrow $ direction.
The proof as presented in the lectures (having already proven that if G has only even degree vertices then it has an Euler circuit) was: suppose our two vertices of odd degree are x and y. If they are not adjacent, then we can add an edge between them, and we can construct out Euler circuit. Removing the dge gives the result.
But suppose that x and y are adjacent. In my lectures, we claim that we can construct a new path between x and y using all new edges.
But I don't see how this can be. For a path of length 2, we need x and y to have a common non-neighbour, which we cannot guarantee. For a path of length general length, we need some i'th degree non-neighbour of x to be a jth degree non-neighbour of y. Where I define an i'th degree non-neighbour to be such that you can contruct a trail with i completely new edges between x and this vertex, z say.
If anyone has any hints that would be much appreciated.
If $x$ and $y$ are adjacent and you are not allowed to go into multigraphs, you add a completely new vertex $z$ connected only to $x$ and $y$, then construct the Euler circuit. Since $z$ is only connected to $x$ and $y$, the edges $x-z-y$ must be adjacent in the circuit thus constructed; removing these edges gives an Euler trail as required.