1
$\begingroup$

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

Or any other restrictions?

How would it look like?

Thanks in advance

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 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
3
$\begingroup$

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.

$\endgroup$
  • $\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
0
$\begingroup$

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$.

$\endgroup$

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.