A proof outline follows:
- Given: Let each space s be a vertex, and let each valid knight jump be an edge. We want to prove that the graph G representing all legal moves for the knight on a m x n chessboard is bipartite.
- Consider partitioning the board into white spaces W and black spaces B. We will show G is bipartite with "sides" W and B.
- A knight on a white space can only jump to a black space, and vice versa.
- So, a knight on a white space cannot jump to another white space; likewise for black.
- (This means that for any two vertices in W, there is no edge connecting them; likewise for black.)
- By definition of a bipartite graph, then, G is bipartite.
-Brian (Thomas34 21:02, 18 November 2008 (UTC))
