This is equal to twice the number of edges in the graph divided by the number of nodes, because each edge is incident on two nodes. For the 100-node graphs we studied, the number of binary nogoods is given by . The colors are considered in a fixed ordering for all of the nodes in the search. As a simple optimization, the search never changes the colors selected for the first two nodes. Any such changes would amount to unnecessarily repeating the search with a permutation of the colors for unsolvable cases.
Search cost is measured by the number of nodes explored.