3 ms·
The chessboard-domino problem isn't related to hamiltonian paths in bipartite graphs. For a minimal counter-example, the path of length 2 is bipartite and has
by anorwell 16y ago
The chessboard-domino problem isn't related to hamiltonian paths in bipartite graphs. For a minimal counter-example, the path of length 2 is bipartite and has a hamiltonian path, but has an odd number of vertices so there is clearly no way to cover it with dominoes. You can also find counter-examples in the other direction (bipartite, domino-coverable, not hamiltonian), but they take a bit more effort to describe.
The generalized chessboard problem is to find a perfect matching (http://en.wikipedia.org/wiki/Perfect_matching http://en.wikipedia.org/wiki/Perfect_matching) in a graph: that is, a set of edges that cover each vertex, but don't touch any other edge in the set. This problem is a lot easier than finding a hamiltonian path, which is NP-complete.
- Locke1689 16y agoWell, they're not related in that they are not the same problem, but they are related in that you can solve both using the properties of bipartite graphs. I think I was correct in the post—I never actually stated that domino-covering is equivalent to the Hamiltonian path problem. The entire point of the post was really that we can use graph theory to generalize certain properties and solve a number of different unrelated problems, not to equate all problems. I did mistakenly imply that the domino covering was a path (which you're right, it's not) at one point. I have edited the post for clarity.