2
$\begingroup$

If we have a Graph with Euler Circuit can we the consider it as a special Euler Path that start and end in the same Node?

I am asking because the Condition of Euler Path is that we have 0 or 2 Nodes with an odd degree so but the graph with 0 nodes with odd degrees will have an Euler Circuit.

$\endgroup$
  • 1
    $\begingroup$ Yes. An Eulerian circuit is a special kind of Eulerian path. $\endgroup$ – Rob Arthan Jul 30 '18 at 21:04
  • $\begingroup$ @RobArthan That is not true. A circuit is not a path. You have to remove an edge to get a path. $\endgroup$ – Morgan Rodgers Sep 20 '18 at 17:24
  • $\begingroup$ @MorganRodgers: opinions seem to vary on this point in graph theory. en.wikipedia.org/wiki/Path_(graph_theory) allows a path to start and end at the same vertex (but, oddly, in my opinion, doesn't allow any other repeats in the vertices). I had never noticed (until you raised your comment) that graph theorists have bizarre prejudices about this terminology that algebraic topologists don't. $\endgroup$ – Rob Arthan Sep 20 '18 at 19:57
  • $\begingroup$ @RobArthan A walk is the term when vertices are possible repeated. But interesting, I did not realize there was debate about the first/last being allowed as identical. $\endgroup$ – Morgan Rodgers Sep 20 '18 at 20:08
1
$\begingroup$

If you take 10 graph theorists then you will have about 50 different definitions of paths and cycles between them.

You should be aware that:

  • If you have a connected graph with exactly $2$ vertices of odd degree, then you can start at one and end at the other, using each edge exactly once, but possibly repeating vertices. This is the only degree condition under which this happens.
  • If you have a connected graph with exactly $0$ vertices of odd degree, then you can start at any vertex and return to that same vertex, using each edge exactly once, but possibly repeating vertices. This is the only degree condition under which this happens.

If you know this, it doesn't matter if you call these Euler paths, Euler circuits, Euler trails, Euler walks, or Euler meandering throughways.

$\endgroup$
  • 1
    $\begingroup$ Interesting! As an innocent whose background is in algebraic topology, I had never realised that "path" or "circuit" might mean something to graph theorists other than a based homotopy equivalence class in a path space or loop space of a graph. $\endgroup$ – Rob Arthan Sep 20 '18 at 20:00
  • $\begingroup$ Taking paths to be based homotopy equivalence classes turns the hard problem of finding Hamiltonian paths into the easy problem of finding spanning trees, which is a drawback if you like hard problems. $\endgroup$ – Misha Lavrov Sep 20 '18 at 21:55
  • $\begingroup$ Thanks for pointing that out: I should have said homotopy equivalence classes relative to the set of all vertices (not just the endpoints). My point is that I wouldn't expect any restrictions on revisiting vertices or edges, but evidently graph theorists are interested in making finer distinctions than algebraic topologists and have invented more complex taxonomies. $\endgroup$ – Rob Arthan Sep 20 '18 at 22:28

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.