2
$\begingroup$

Let $G$ be a Graph that have Eulerian Cycle and Hamiltonian Path, does it mean that $G$ must have Hamiltonian Cycle?

I tried to find a counter example but I always got stuck since when I notice an Eulerian Cycle I always find a Hamiltonian Cycle. I know that if $G$ have Eulerian Cycle then all the degrees are even, and we visited all the edges exactly one but it doesn't necessary means that we have visited all the vertices exactly once.

I will be happy if someone can help by getting a counter example or a proof if its true.

$\endgroup$

1 Answer 1

3
$\begingroup$

Take two cycles sharing one vertex. The resulting graph looks like a bowtie (at least for two $3$-cycles – MathWorld calls it the butterfly graph and it has $5$ vertices) and clearly has a Hamiltonian path and Eulerian cycle, but no Hamiltonian cycle.

$\endgroup$
6
  • 1
    $\begingroup$ Sort of confused... Wouldn't the vertices in the original cycles now have degree 3? My thought was that a minimal counter-example has to have at least 9 nodes --- We know that every vertex has even degree, so the degree is at least 4 (as o.w. any graph meeting the requirements is a cycle). By Dirac's theorem, we also know that any counter example has at least 9 nodes (min-degree >= ceil(n/2) implies hamiltonian). $\endgroup$
    – mm8511
    May 26, 2021 at 15:24
  • 3
    $\begingroup$ @mm8511 The new graph has a cut-vertex; that vertex has degree $4$ and all other ones have degree $2$. Having a cut-vertex is by itself enough to preclude a Hamiltonian cycle. $\endgroup$ May 26, 2021 at 15:27
  • $\begingroup$ @ParclyTaxel Can you simplify "identify one vertex from each cycle (i.e. a new vertex is created adjacent to all vertices adjacent to either of the two chosen ones)" ? what do you mean? How many vertices in the minimalist graph that is considered as a counter example? $\endgroup$
    – Fox
    May 26, 2021 at 15:37
  • $\begingroup$ @ParclyTaxel But in the Butterfly Graph there is No Hamiltonian Path! $\endgroup$
    – Fox
    May 26, 2021 at 15:52
  • $\begingroup$ @Fox Have you tried finding a Hamiltonian path? It's pretty easy. $\endgroup$ May 26, 2021 at 15:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .