In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move.

[1] It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner.

It can also be constructed as the strong product of two path graphs.

king's graph the total number of vertices is

king's graph this simplifies so that the total number of vertices is

and the total number of edges is

[3] The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata.

[4] A generalization of the king's graph, called a kinggraph, is formed from a squaregraph (a planar graph in which each bounded face is a quadrilateral and each interior vertex has at least four neighbors) by adding the two diagonals of every quadrilateral face of the squaregraph.

[5] In the drawing of a king's graph obtained from an

crossings, but it is possible to obtain a drawing with fewer crossings by connecting the two nearest neighbors of each corner square by a curve outside the chessboard instead of by a diagonal line segment.

For the king's graph of small chessboards, other drawings lead to even fewer crossings; in particular every