The knight attack graph has one vertex per chessboard square and an edge between squares linked by a knight move. A nonattacking placement is an independent set. Colouring squares by the parity of the coordinate sum makes this a bipartite graph, because every knight move changes that parity. Every vertex has degree at most eight, with fewer attacks near the boundary.
New to topics? Read the docs here!