[Math] Hamiltonian and non-Hamiltonian connected graph using the same degree sequence

graph theoryhamiltonian-path

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:

           *——*——*                *      *  
           |  |  |                |\    /|  
           *——*——*                | *——* |  
                                  |/    \|  
                                  *      *
Related Question