Fix a board where the height and width are greater than 2. A valid walk on a board is to start on one square and move to a vertically or horizontally adjacent square, so diagonal traversals are not allowed. A tour is a valid walk such that each square is touched exactly once and the walk begins and ends on the same square. Prove that if either the height or width is even, a tour exists. Also prove that if p and q are odd, there is no tour.

First, I prove that this "board" is merely a bipartite graph. Let $V_{i,j}$ be a cell on the graph where $i,j \ge 0$ and $i,j \in \mathbb{Z}^+$. If $i$ is even and $j$ is even, color the cell $c_1$. If $i$ is even and $j$ is odd, color the cell $c_2$. If $i$ is odd and $j$ is odd, then color the cell $c_1$. If $i$ is odd and $j$ is even, color the cell $c_2$. Note that the board is two-colored, which is a bipartite graph.

Claim 2: If the height and width are odd, a tour doesn't exist.

  1. Assume by contradiction that a tour exists.
  2. If the height and width are both odd, the total number of cells (or vertices) is also odd.
  3. A tour on a graph of odd vertices would be of odd-length.
  4. This is a contradiction because bipartite graphs only contain even-length cycles, so such a tour cannot exist.

I'm unsure of a couple of things, which I hope someone can clear up:

  1. Am I interpreting this question right by converting it into a bipartite graph?
  2. Is the proof for Claim 2 correct? If not, how can I optimize it?
  3. How would I approach proving Claim 1? I was thinking that if there are an even number of vertices in the graph and the two bipartitions have an equal number of vertices in them, a tour might exist. However, I'm not sure how to formulate this into better words.
  • 2
    $\begingroup$ What you’ve done so far is fine. For the rest, see my answer to this question. $\endgroup$ – Brian M. Scott Oct 26 '16 at 21:35
  • 1
    $\begingroup$ The coloring can be used to demonstrate that this board can be regarded as a bipartite graph, and you have used that to good effect to prove the second statement. For the first statement, you might be able to simply demonstrate how to construct a valid tour. $\endgroup$ – Joffan Oct 26 '16 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.