Does this graph have a Hamiltonian cycle?

234 Views Asked by At

My gut feeling is to say no because this is a bipartite graph with an unequal partition of vertices $(3,1,3)$. However, I am not sure if the exact logic applies because of the line going through above the center as well. Could that suggest that the partitioning is actually different? I still think no but I just want some verification.

Any help?

1

There are 1 best solutions below

0
On BEST ANSWER

Your reasoning is wrong: $(3,1,3)$ is not a bipartition at all.

However, the graph still has no Hamiltonian cycle because it is bipartite and has an odd number of vertices. Any Hamiltonian cycle in a bipartite graph must necessarily have an even number of vertices; given a 2-colouring of the graph, all such cycles will alternate colours.