# An Eulerian graph without an arbitrary trail is connected?

Let $G=(V,E)$ be an Eulerian graph. We say that a vertex $v$ in $V$ is a generator if every trail beginning in $v$ can be extended to form an Eulerian circuit.

For this we will only consider simple graphs.

I need to prove that if $G-v$ is a forest then $v$ is a generator.

So, I already proved that if $G-v$ is a forest, $v$ must be connected to every edge of odd degree on $G-v$ for if not there would be a vertex of odd degree in $G$ and that contradicts the hypothesis of $G$ being Eulerian (given that any graph has an even number of vertices with an odd degree this ensures that $v$ has an even degree), and this are the only edges incident on $v$.

Now, let $S$ be an arbitrary trail beginning in $v$.

I want to prove that the graph is still connected when we remove all the edges of $S$ and all the vertices which all its edges are in $S$, because then I will have a graph that is connected and has exactly 2 vertices of odd degree which will be $v$ and the last vertex of $S$ so then is semi-eulerian which means there exists an eulerian path that exhausts all of its edges beginning in the last vertex of $S$ and ending in $v$.

I have tried to prove the connectedness of the remaining graph using the fact that they can be connected to $v$ but I don't know how to ensure that all the vertices of $v$ haven't been used yet by the trail.

I would appreciate very much any hint, clue or advise you can give me.

• Can even someone tell me if is true that the remaining graph is connected? – mathstu15 Nov 3 '14 at 21:03
• The term generator is also new for me, but you can see that it is defined in the beginning of the question "vertex v in V is a generator if every trail beginning in v can be extended to form an Eulerian circuit" and a trail is a walk – mathstu15 Nov 3 '14 at 22:24
• According to wikipedia, a trail is a walk with distinct edges. This is essential for the prove. Did you use this property ? – Peter Nov 3 '14 at 22:34
• Yes but precisely, the fact that they could leave a group of edges disconnected is what could give me trouble, even though I think this is not possible but I still don't know why – mathstu15 Nov 4 '14 at 1:37