How do I know that a Knight's tour forms a bipartite graph?

Question

I understand that a knight's tour can be represented as a bipartite graph. Using colours, the odd moves can be coloured black and the even moves white. Drawing it out myself, I see that I do get a 2-colourable graph.

However, how does one mathematically prove that a knight's tour always results in a bipartite graph?

Answer 1

You have already proved it

The definition of a bipartite graph (Wikipedia) is:

a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets $U$ and $V$ such that every edge connects a vertex in $U$ to one in $V$

A knight can be on either a white square or a black square. If we let $U$ be the set of white squares that the knight visits, and $V$ the set of black squares that the knight visits, then:

• $U$ an $V$ are clearly disjoint (they contain no common elements)

• every edge (move) necessarily goes from a white square to a black square, or vice-versa. Therefore, every edge connects a vertex in $U$ with a vertex in $V$

So our graph satisfies the definition of a bipartite graph.

Answer 2

Adding to @wimi answer, another characterization of bipartite graphs is

A graph is bipartite iff it contains no odd cycle.

By noticing knight can create a cycle of length $2$, and proving it can not start from some position, and return to it and exactly $3$ moves, one can prove any knight does not contain an odd cycle, and there for a bipartite graph.