Tour de Knight

We will show that 3 cases are not possible, and that the $5 \times 6$ case is possible.

1) The $7 \times 7$ case, more generally the odd X odd case.
If we color it in the usual chessboard format, say with Black and White squares, we know that the knight must move in the form B-W-B-W-B-W-.... . Hence, the number of Black and White square must be the same, which means that the total number of squares is even. But, there are an odd number of squares, hence contradiction.

2) The $4 \times 5$ case, more generally the $4 \times m$ case.
Align the board so that each column has 4 squares.
If we color the top and bottom rows Green, and the middle rows Red, we see that from a Green square we can only go to another Red square, (while we can go from a red square to a red or green square). Since there are an equal number of black and white squares, the closed tour must be of the form R-G-R-G-R-G, etc Now, if we color it in the usual chessboard format, say with Black and White squares, we know that the knight must move in the form B-W-B-W-B-W-B-W.
Hence, in a tour, it must be of the form RB-GW-RB-GW ... or RW-GB-RW-GB .... In either case, we clearly cannot hit half of the squares.

3) The $3 \times 8$ case - This requires more work.

Proof by contradiction. Suppose that a path exists.
Since the corner cells $(1,1), (1,3 ), (8,1), (8,3)$ are only connected to 2 squares each, the tour involving these squares are forced (path is in green).
Similarly, since the cells $(1,2), (2,2), (7,2), (8,2)$ are only connected to 2 squares each, the tour involving these squares are forced (path is in pink).
The remaining possible knight moves are shown in purple.

We define a new graph $G$ . First, we define the 8 paths given by the 2 green paths, 4 pink paths, the trivial path consisting of the vertex (2,4) and the trivial path consisting of the vertex (2,5). These 8 paths will form the 8 vertices of our new graph. The edges of these graphs are indicators of possible knight moves from the endpoint of a vertex-path to any endpoint of another vertex-path. Then, a closed knights tour on $3 \times 8$ will yield us a closed walk that goes through all vertices ( hamiltonian path ) on this new graph (though not necssarily vice-versa). This is what it looks like:

We can easily verify that there is no closed walk that covers all vertices. Hence, there is no solution to the $3 \times 8$ graph.

4) The $5 \times 6$ case

The graph shows the knight's path.

---

The actual theorem:

For any $m \times n$ chessboard with $m \leq n$ , a closed knight's tour is always possible unless one or more of these three conditions are met:

1. $m$ and $n$ are both odd
2. $m$ = 1, 2, or 4
3. $m$ = 3 and n = 4, 6, or 8.

The $(3,8)$ case is the hardest to deal with, and I encourage you to show that the other cases are not possible.
Showing that all over cases are possible requires some work.

Here is the original paper by Schwenk.