Knight attack graph
= Knight attack graph
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.