0
$\begingroup$

How would one illustrate a graph that has both an Euler cycle and a Hamiltonian cycle, but they are not the same?

From what I read, the Euler cycles themselves must have included edges and vertices, and Hamiltonian must have included only vertices? If this is the case that makes no sense to me how to draw that specifically including both without them being the same cycles.

$\endgroup$
1
$\begingroup$

The Hamiltonian cycle does not have to use every edge, but must visit each vertex exactly once. The Eulerian cycle is allowed to visit a vertex multiple times, but must visit each edge exactly once.

An example would be $K_5$. A Hamiltonian cycle is just "draw a loop around the outside". The Eulerian cycle would be "draw that loop, then a pentagram".

$\endgroup$
1
$\begingroup$

The complete graph $K_5$ has both Euler circuits and a Hamiltonian cycles. An Euler circuit in $K_5$ uses all ten edges; it is not a cycle. A Hamiltonian cycle in $K_5$ is a $C_5$; it uses only five of the ten edges in $K_5$.

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