0
$\begingroup$

Problem: Show that every nontrivial connected graph $G$ has a closed spanning walk that contains every edge of $G$ exactly twice.

My Attempt: I've tried to consider two cases. First $G$ is Eulerian, then we have a Eulerian Circuit $C$, which could simply be traversed again. Next, suppose that $G$ is not Eulerian. In this case, consider the graph $G$ with additional edges $(u,v)$, where $u$ and $v$ are odd vertices. Then we have a graph which has essentially all vertices of even degree and so we obtain a Eulerian Circuit $C_1$. Now we delete all the edges thata re incident with odd vertices from this graph and thus we are left another subgraph $H$ which has all even vertices giving us another circuit $C_2.$ I claim that $C_1$ and $C_2$ cover all edges twice but I can't prove it. Please help.

$\endgroup$
2
$\begingroup$

You might be able to make something like that work, but there's an easier way. Just double every edge: then every vertex certainly has even degree, so the graph is now Eulerian, and an Euler circuit on the new graph easily translates to a walk on $G$ that traverses each edge exactly twice.

$\endgroup$
  • $\begingroup$ Ooh! Pretty cool. Thank you, sir. $\endgroup$ – model_checker Dec 9 '16 at 13:27
  • $\begingroup$ @Supermario: You're welcome. $\endgroup$ – Brian M. Scott Dec 9 '16 at 13:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.