# how to construct a closed trail starting at a given vertex and show it exists in an eulerian graph

Problem: Let $G$ be an eulerian graph.

$(a)$ Explain in detail how to construct a closed trail starting at a given vertex $x$ of $G$. Prove that such a trail exists for every $x \in V (G)$ (the vertice set of $G$).

My attempt: a) First order the vertices of the graph, say $\{v_1,...,v_n\}$. Next I would proceed in order so that if there is an edge connecting $v_i, v_j$ where $j=i+1, 1\leq i \leq n$ then add it to the trail, otherwise continue for $j=i+2$, etc. until you have a path to the $v_n$, and then return backwards doing the same thing but for edges not added to the path where now $v_i, v_j$ form an edge with $j=i-1$ for $i-j<n-1$ until you return to $v_1$.

I am not sure how to show that such a trail exists however. Any hints appreciated.

Edit: My definitions from my notes:

An Euler trail in a graph is a trail that contains every edge of the graph. An Euler tour is a closed Euler trail. A graph is called eulerian is it has an Euler tour

• Isn't "connected" redundant in "connected Eulerian graph"? By definition, an Eulerian graph is a graph which has a Euler circuit, which implies that it is connected. – bof Feb 24 '17 at 22:54
• @bof sure, edited. – IntegrateThis Feb 24 '17 at 22:56
• I don't get it. To prove the existence of a closed trail starting at a given vertex $x,$ why don't you just take an Euler circuit and follow the circuit starting from $x?$ – bof Feb 24 '17 at 23:00
• Maybe I was wrong in thinking "Eulerian" implies "connected". Does the definition of Eulerian graph permit isolated vertices? – bof Feb 24 '17 at 23:01
• Maybe "Eulerian" in this context means "Each vertex has even degree"? At any rate, they're asking for an explicit construction. – Arthur Feb 24 '17 at 23:03

If the graph is Eulerian, then note that if you just start at $x$ and walk an arbitrary path, you must eventually end up back at $x$ at some point, making a (not necessarily Eulerian) loop.
Next, if the path is Eulerian, then rejoice, for you are done. If not, then there must be some vertex $y$ along the chosen path that has unused edges. Start at $y$, and along the same lines as the paragraph above, make a loop that starts and ends at $y$, using only edges that wasn't used by the original $x$-loop. Now take the original loop, when you get to $y$, do the $y$-loop, then continue along the original loop after that. You have now created a longer loop.
• Why is it true that you "must eventually" end up back at $x$ at some point. – IntegrateThis Feb 24 '17 at 23:05
• That's why I called this a sketch. Here are three questions to get you started: At any point as you walk along the path, if you are not back where you started, how many (and which) vertices have an odd number of unused edges? Is $0$ an odd number? Does this mean you can take another step? – Arthur Feb 24 '17 at 23:09