 In the Hajós construction itself, the new edge forces at least one of the two vertices and to have a different color than the combined vertex for and , so any proper coloring of the combined graph leads to a proper coloring of one of the two smaller graphs from which it was formed, which again causes it to require colors.Hajós proved more strongly that a graph requires at least colors, in any proper coloring, if and only if it contains a -constructible graph as a subgraph.Equivalently, every -critical graph (a graph that requires colors but for which every proper subgraph requires fewer colors) is -constructible.