Is there any regular, balanced, connected bipartite graph that does not contain any Hamiltonian cycle?

636 Views Asked by At

In a set of balanced, connected bipartite graphs, all with regularity $r \ge 2$, is it possible that there exists a bipartite graph that does not contain a Hamiltonian cycle ?

My argument: The bipartite graph is balanced, so both of the partition has the same number of vertices. It's regularity $r \ge 2$ and the graph is connected, that means we can switch between the partitions, so there is a Hamiltonian path. Lets say that we have followed the Hamiltonian path from vertex $u$ and reached to a vertex $v$ and exhausted all the vertices, now how do I prove that there must be an edge that will take me back to $u$ from $v$?

I am getting lost with this construction of the "Hamiltonian cycle".

So does this mean that there can be such bipartite graph (connected, balanced, $r \ge 2$ regular) that does not contain a Hamiltonian cycle? If yes, can someone give me a concrete example?

N.B.: $r$-regular: every edge is $r$-degree.

1

There are 1 best solutions below

3
On BEST ANSWER

Here is a concrete non-Hamiltonian 3-regular bipartite graph:

          -----X-----
         /     |     \
        O      O      O
       / \    / \    / \
      X-O-X  X-O-X  X-O-X
      | | |  | | |  | | |
      O-X-O  O-X-O  O-X-O
       \ /    \ /    \ /
        X      X      X
         \     |     /
          -----O-----