An Eulerian graph without an arbitrary trail is connected?

71 Views Asked by At

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.