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.

  • $\begingroup$ Can even someone tell me if is true that the remaining graph is connected? $\endgroup$ – mathstu15 Nov 3 '14 at 21:03
  • 1
    $\begingroup$ 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 $\endgroup$ – mathstu15 Nov 3 '14 at 22:24
  • $\begingroup$ According to wikipedia, a trail is a walk with distinct edges. This is essential for the prove. Did you use this property ? $\endgroup$ – Peter Nov 3 '14 at 22:34
  • $\begingroup$ 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 $\endgroup$ – mathstu15 Nov 4 '14 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.