Suppose that in the definition of an Euler cycle, we drop the seemingly superfluous requirement that the Euler cycle visit every vertex and require only that the cycle include every edge. Show that now the theorem is false. Draw a graph that illustrates why the theorem is false.

I guess I might think of it this way: we could not have odd degree vertices, and now we don't need to visit those odd degree vertices. But I guess I'm confused because it seems like we still do, because we still need to cover the edges that connect those vertices.

  • 2
    $\begingroup$ What does the theorem of the euler cycle say explicitly? please copy it word for word. $\endgroup$ – Jorge Fernández Hidalgo Feb 14 '15 at 18:34
  • $\begingroup$ A multigraph has an Euler cycle if and only if it is connected and has all vertices of even degree. $\endgroup$ – Chylomicron Feb 14 '15 at 18:36
  • 1
    $\begingroup$ How can you traverse the edge $\{a, b\}$ without visiting both endpoints? I think crossing all edges implies that you'll visit all vertices; if you don't visit all vertices, there's no way you can cross all the edges. $\endgroup$ – pjs36 Feb 14 '15 at 18:46
  • $\begingroup$ @MJD Got it. Had to look up the book to see how everything was worded, but I see. Chylomicron, how could we possibly cross all edges of the graph without visiting all vertices? For the theorem to be false, the graph would either need to be disconnected, or have at least one vertex of odd degree, yet still have a cycle that includes all edges. $\endgroup$ – pjs36 Feb 14 '15 at 21:36
  • $\begingroup$ Ohhh. I see it now. Now I feel silly. I kept thinking, "but it can't be just that it's disconnected, because then you have a vertex of degree zero, which is still even, so that doesn't disprove the theorem!" Really it just had to be disconnected, because that alone disproves the theorem. Thank you for the help! $\endgroup$ – Chylomicron Feb 15 '15 at 18:01

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.