A closed Knight's Tour does not exist on some chessboards

Question

It is generally difficult to determine whether a (large) graph have no Hamilton cycle (As opposed to determining whether it has any Euler circuit). This example illustrates a method (which sometimes work) to indicate that a graph has no Hamilton cycle.

a. Show that if m and n are odd integers (not both = 1), a Knight is not in Following features visit all the squares on an m × n 'chessboard' just once, return to the starting point. (A knight goes in a move two squares forward and one to the side.)

b. Show the same thing for a board of size 4 × n, n integer.

I know when is a hamilton cycle we visit every vertirce in the graph. I draw this in paint but i was very weird?? Somebody with a hint?

Answer 1

Both parts are well-known (see, for instance, Theorem in [Schw], and short proofs in [GT]) and easy to prove.

a. It is well-known that the chessboard cells are colored black and white and when Knight moves it changes color of its cell. Therefore each Hamiltonian Knight cycle on the chessboard has an equal numbers of black and white cells. So if such a cycle exists then the chessboard also has an equal numbers of black and white cells, which doesn’t hold when both $m$ and $n$ are odd. Or see Theorem 2.5 from [McG,L].

b. See, for instance, Theorem 3.15 from [McG,L]

References

[GT] Rob Gaebler, Tsu-wang Yang, Knight's Tours (August 13, 1999).

[McG,L] Kevin McGown, Ananda Leininger, Knight’s Tour.

[Schw] Allen J. Schwenk, Which Rectangular Chessboards Have a Knight's Tour?, Mathematics Magazine, Vol. 64, No. 5 (Dec., 1991), pp. 325-332.

Additional references

http://www.borderschess.org/KnightTour.htm

http://users.cecs.anu.edu.au/~bdm/papers/knights.pdf

http://blog.wolfram.com/2014/09/04/solving-the-knights-tour-on-and-off-the-chess-board/

http://www.sciencedirect.com/science/article/pii/S0166218X04003488

http://algorithms.tutorialhorizon.com/backtracking-knights-tour-problem/

Answer 2

There's a really pretty proof for part (b), which the accepted answer does not do justice to by hiding it under links.

We consider two colorings of the $4 \times n$ board. The first is the usual black and white coloring:

Each knight move must be to a square of another color, so the colors alternate black-white-black-white in any knight's tour.

The second coloring is to color the top and bottom rows blue and the middle rows orange:

From a blue square, a knight can only go to orange squares. The reverse is not true, but in a closed tour, there are $2n$ blue squares and $2n$ orange squares, and blue squares cannot be adjacent, so the colors alternate blue-orange-blue-orange in any closed tour.

Assume for contradiction that a closed knight's tour exists. We can start the closed tour anywhere we like, so let's start at the top left square, which is white in the first coloring and blue in the second. Both groups of colorings alternate, so the next square is black/orange, the one after that is blue/white again, the one after that is black/orange again, and we can never get to a white/orange or black/blue square.

So a closed knight's tour cannot exist.