Determining Information about a Graph Using the Degree Sequence

679 Views Asked by At

Let the following sequence be the degree sequence of the vertices of a graph with $n=10$ vertices.

$\{6,6,4,4,4,4,2,2,2,2\}$

Is it possible to determine from this information whether this graph cannot be Hamiltonian or planar?

With regard to being Hamiltonian, I have been trying to find theorems that apply to this graph and I haven't, so my inclination is to say there is not enough information.

To find if it is planar, I have a feeling it is possible and tried, unsuccessfully, to draw graphs. The two theorems that can say for sure it cannot be planar do not apply.

EDIT: I found a planar graph so I know it is possible.

1

There are 1 best solutions below

1
On BEST ANSWER

Here are two different graphs with the desired degree sequence, one is Hamiltonian and non-planar, and the other is non-Hamiltonian and planar.