 More specifically, define the Hajós number of a -chromatic graph to be the minimum number of steps needed to construct from , where each step forms a new graph by combining two previously formed graphs, merging two nonadjacent vertices of a previously formed graph, or adding a vertex or edge to a previously formed graph.They showed that, for an -vertex graph with edges, .If every graph has a polynomial Hajós number, this would imply that it is possible to prove non-colorability in nondeterministic polynomial time, and therefore imply that NP = co-NP, a conclusion considered unlikely by complexity theorists.