# Knights tour on a 4 x m board

Prove that on a chessboard that has dimension $4 \times m$ there doesn't exist a knights tour in which we return to square we started at.

I know that we need to turn each square into a vertice and then add edges between vertices where a valid move exists. Now we must show that this graph is not Hamiltonian, which I am unsure how to do. Any help is appreciated, thanks!

HINT

Show that since you can't move between rows 1 and 4, in a (supposed!) Tour you can't move between rows 2 and 3 either.

So, what are all the colors of the squares visited in rows 2 and 3 like in such a Tour?

• The only thing I am seeing is that they all have degree 3, other than that I am unsure how to proceed. – Justin Stevenson Mar 20 '17 at 22:45
• Ah, right, I was confused with an Eulerian cycle :( – Bram28 Mar 20 '17 at 22:47
• @JustinStevenson Ok, new HINT! – Bram28 Mar 20 '17 at 23:20
• Why can't you move between row 2 and 3? – Justin Stevenson Mar 20 '17 at 23:57
• Not if you want a Hamiltonian tour ... how many squares are there in rows 1 and 4? How many are there in rows 2 and 3? – Bram28 Mar 21 '17 at 0:24

You can solve this through colouring the squares like so

1 B 1 B 1 B 1 B ...
2 A 2 A 2 A 2 A ...
A 2 A 2 A 2 A 2 ...
B 1 B 1 B 1 B 1 ...


You start from the top left corner with colour $$1$$. Every field $$1$$ is preceeded and followed by a $$2$$. Because every field has to be in the tour, all $$1$$'s and $$2$$'s are in the sequence of moves, whereby the number of $$1$$'s and $$2$$'s are the same.

But the $$A$$'s must also lie in the sequence. In order to do that, there are only these two cases:

• Case 1: To get to an $$A$$, you are coming from a $$2$$. In this case, to get to a $$1$$, you have to go to a $$2$$ first in oder to do that, i.e. you have more $$2$$'s then $$1$$'s. Contradiction. An example would be like $$\ldots \rightarrow \underline{1 \rightarrow 2} \rightarrow A \rightarrow \boxed2 \rightarrow \underline{1 \rightarrow 2} \rightarrow \ldots$$ or like $$\ldots \rightarrow \underline{1 \rightarrow 2} \rightarrow \underline{A \rightarrow B} \rightarrow A \rightarrow \boxed2 \rightarrow \underline{1 \rightarrow 2} \rightarrow \ldots$$ Note that the boxed $$2$$ isn't in a pair with a $$1$$.

• Case 2: To get to an $$A$$, you are coming from a $$B$$. Like the $$1$$'s, every $$B$$ is preceeded and followed by an $$A$$. Therefore, to get to this $$B$$, you have to come from an $$A$$, so there is no first $$A$$ you moved to. Contradiction.

Therefore there is no colosed tour on the board.

Additional note: This solution is from the excellent and highly recommended book Problem-Solving Strategies by Arthur Engel. Some olympiad problems you will face come from this book. There's also a lot of must-no-theory in there. Give it a try: PDF link.