Hamiltonian and non-Hamiltonian connected graph using the same degree sequence

1.5k Views Asked by At

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?

2

There are 2 best solutions below

0
On BEST ANSWER

The degree sequence $\langle 3,3,2,2,2,2\rangle$ will work:

           *——*——*                *      *  
           |  |  |                |\    /|  
           *——*——*                | *——* |  
                                  |/    \|  
                                  *      *
0
On

The idea is that one of them has a central vertex or edge such that removing it leaves the graph not connected.

When I solved the exercise I found a bigger example than $(2,2,3,3,3,3)$, where the two graphs have score $(2,2,3,3,3,3,4)$: one is $C_6$ with a central vertex of degree 4, the other is a double $K_3$, with the extra vertex of degree 4 connected to 2 vertices of the first $K_3$ and to 2 vertices of the other one.