Chapter 10, Problem 32SE

A simple graph can be used to determine the minimum number of queens on a chessboard that control the entire chessboard. An $n\times n$chessboard hasn²squares in an $n\times n$configuration. A queen in a given position controls all squares in the same row, the same column, and on the two diagonals containing this square, as illustrated. The appropriate simple graph hasn²vertices, one for each square, and two vertices are adjacent if a queen in the square represented by one of the vertices controls the square represented by the other vertex.

*32.How many nonisomorphic simple connected graphs with five vertices are there

a) with no vertex of degree more than two?

b) with chromatic number equal to four?

c) that are nonplanar?