0
$\begingroup$

I am trying to decide whether it is possible to have two graphs with the same degree sequence where both are connected, but only one has a Hamiltonian cycle. Can anyone give me an example?

It is obvious to find examples when one is connected and one is disconnected, however I am unable to come up with anything for this case.

$\endgroup$
5
$\begingroup$

The degree sequence $3,3,2,2,2,2$ can be realized by a hexagon with a chord, or by two triangles with a bridge between them. One is Hamiltonian, the other is not.

$\endgroup$
  • $\begingroup$ Does either have a Hamiltonian cycle ie starting and ending at the same vertex? $\endgroup$ – Mark Mar 21 '15 at 10:59
  • $\begingroup$ Yes, the hexagon with a chord; if you erase the chord, what's left is a Hamiltonian cycle. $\endgroup$ – bof Mar 21 '15 at 11:03
1
$\begingroup$

Take the following two graphs $G$ and $H$ with the same degree sequence 3,3,2,2,2. $H$ is Hamiltonian while $G$ is not.

enter image description here

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