I'm trying to find out if it is possible to construct a connected Hamiltonian and a connected non-Hamiltonian graph using the same degree sequence.
For disconnected graphs it would be easier, I could choose a degree sequence of $(2,2,2,2,2,2)$ and have $C_6$, which has a Hamiltonian path, and two disjoint 3-cycles, which are non-Hamiltonian.
How to do it with two connected graphs?
Best Answer
The degree sequence $\langle 3,3,2,2,2,2\rangle$ will work: