If so does it force it to be a simple circle?

Or any other restrictions?

How would it look like?

Thanks in advance


A path is Hamiltonian if each vertex is visited exactly once. A path is Eulerian if every edge is traversed exactly once. Clearly, these conditions are not mutually exclusive for all graphs: if a simple connected graph $G$ itself consists of a path (so exactly two vertices have degree $1$ and all other vertices have degree $2$), then that path is both Hamiltonian and Eulerian. If $G$ is a cycle, then that cycle is Hamiltonian and Eulerian.

  • 1
    $\begingroup$ Thanks does that path have to be a simple circle? cant think on a way to draw it as not simple $\endgroup$ – The One Jun 27 '14 at 14:18

The answer is yes.

We have two criteria to meet:

$1.$ Have either $2$ odd vertices or have none at all.

$2.$ Travel to each vertex once and only once, and return to the starting point.

These can both be met, and an example is:

eulerian hamiltonian graph

(Source: "Eulerian and Hamiltonian Graphs", Mathematics Learning Center, p.3)

Note: I have assumed for criteria $2$ that you are referring to a Hamiltonian circuit.

  • $\begingroup$ Thanks yea i meant a circuit, does it have to be a simple circuit? $\endgroup$ – The One Jun 27 '14 at 14:39
  • $\begingroup$ @kfir124 If it wasn't a simple circuit, then by definition it would visit some vertex more than once, and so it wouldn't be hamiltonian. $\endgroup$ – MJD Jun 27 '14 at 15:09
  • $\begingroup$ I think we need to be clear on what the question is asking. The OP asked, "can a path be Hamiltonian and Eulerian at the same time." Your answer addresses a different question, which is "can a graph be Hamiltonian and Eulerian at the same time." $\endgroup$ – heropup Jun 27 '14 at 15:27
  • $\begingroup$ The graph in the figure is both Hamiltonian and Eulerian, but the Eulerian path (circuit) visits some nodes more than once, and the Hamiltonian cannot visit all nodes. $\endgroup$ – SOFe Dec 9 '18 at 15:16

To set the record clear: Yes.

A Path can be both Eularian and Hamiltonian. A Hamiltonian path is a spanning path, and an Eularian path goes through each edge exactly once. To consider a path holding both properties at the same time, think of the maximal path in $P_n$.


Your Answer

