Let $G=(V,E)$ be a graph. Its edges can be divided into several groups such that each group has a Hamiltonian Circuit of the original graph $G$.

Does $G$ have an Eulerian Circuit?

I said yes.

If each group of edges has a Hamiltonian Circuit, every group of edges has all the vertices of the original graph $G$.

Let $v$ be one such arbitrary vertex.

Starting with some group, it has the Hamiltonian Circuit: $$(v=v_0,v_1\ldots v_n-1,v_n = v)$$ So we are back at $v$, onward to the next group, again with a circuit starting and ending at $v$, until all edges have ben covered.

The reason that the resultant path is an Eulerian Circuit is because every edge has been visited and only once, as no edge is in two groups because we have divided them into seperate groups.

And of course, we started and finished at $v$

Am I correct or is my reasoning flawed and there is a counter example?


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.