1
$\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$

1 Answer 1

3
$\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$
2
  • $\begingroup$ Ooh! Pretty cool. Thank you, sir. $\endgroup$
    – Student
    Dec 9, 2016 at 13:27
  • $\begingroup$ @Supermario: You're welcome. $\endgroup$ Dec 9, 2016 at 13:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .