Euler & Hamiltonian Cycles

891 Views Asked by At

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.

2

There are 2 best solutions below

0
On

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

0
On

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