New answers tagged

1 vote

Is this graph Hamiltonian?

Building from Gordon's answer, we can add one more vertex to his graph and join it to all five vertices of degree 4, as shown in the figure below, vertex 10 is the one added. This gives us six ...
user avatar
  • 219
20 votes
Accepted

Is this graph Hamiltonian?

Here is a 9-vertex graph with degree sequence 4 4 4 4 4 3 3 3 3 that does not have a Hamilton cycle (because it is bipartite on an odd number of vertices). Edit: Here is one line of SageMath showing ...
user avatar
  • 11.2k

Top 50 recent answers are included