Knight's Tour Problem

Another problem that arises in graph theory is called the knight's tour problem. In the game of chess, the chess piece known as the knight can move across the board in either $2$ squares horizontally and $1$ square vertically, or $1$ square horizontally and two squares vertically as represented in the diagram below:

The blue squares represent the possible positions that the knight can move given it's position. So the question is, "Can a knight visit each square of a chessboard exactly once and return to the starting square if the chessboard is of size $m \times n$ ?"

The answer is that only certain chessboards of size $m \times n$ have solutions. For example, let's look at a Knight's Tour for a $4 \times 4$ board where we represent the squares by vertices and the path the knight takes by an edge:

Notice that the only way for the knight to reach both corners of the board is to start on either of the corners. Hence, let's arbitrarily start at the vertex incident to the blue and purple edge. The knight can either travel to vertex $a$ or $b$ (which is symmetrically the same) and then travel to the other corner of the board. However, then the knight must travel to vertex $a$ or $b$ again (the opposite from the vertex picked originally). But then the only two vertices returning to the corner of the board have been used, so the knight cannot return to its start square. Hence there is no knight's tour on a $4 \times 4$ board.

Now let's look at a $5 \times 5$ board:

Once again, no knight's tour start. The only way for us to reach every corner of the board is by the vertices $a$, $b$, $c$, or $d$. Starting at the corner of the board and traversing along, we eventually get to vertex $d$ without filling up all of the other squares first. Hence both vertices $a$ and $d$ were used, so we cannot return to the start point.

Actually, no knight's tours exist on an $m \times m$ board where $m$ is an odd integer, and no knight's tours exist on a $4 \times 4$ board as we examined earlier.