Let and be two undirected graphs, be an edge of, and be an edge of. Then the Hajós construction forms a new graph that combines the two graphs by identifying vertices and into a single vertex, removing the two edges and, and adding a new edge. For example, let and each be a complete graph on four vertices; because of the symmetry of these graphs, the choice of which edge to select from each of them is unimportant. In this case, the result of applying the Hajós construction is the Moser spindle, a seven-vertex unit distance graph that requires four colors. As another example, if and are cycle graphs of length and respectively, then the result of applying the Hajós construction is itself a cycle graph, of length.
Constructible graphs
A graph is said to be -constructible when it formed in one of the following three ways:
The complete graph is -constructible.
Let and be any two -constructible graphs. Then the graph formed by applying the Hajós construction to and is -constructible.
Let be any -constructible graph, and let and be any two non-adjacent vertices in. Then the graph formed by combining and into a single vertex is also -constructible. Equivalently, this graph may be formed by adding edge to the graph and then contracting it.
Connection to coloring
It is straightforward to verify that every -constructible graph requires at least colors in any proper graph coloring. Indeed, this is clear for the complete graph, and the effect of identifying two nonadjacent vertices is to force them to have the same color as each other in any coloring, something that does not reduce the number of colors. 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 is -constructible. Alternatively, every graph that requires colors may be formed by combining the Hajós construction, the operation of identifying any two nonadjacent vertices, and the operations of adding a vertex or edge to the given graph, starting from the complete graph. A similar construction may be used for list coloring in place of coloring.
Constructibility of critical graphs
For, every -critical graph can be generated as a -constructible graph such that all of the graphs formed in its construction are also -critical. For, this is not true: a graph found by as a counterexample to Hajós's conjecture that -chromatic graphs contain a subdivision of, also serves as a counterexample to this problem. Subsequently, -critical but not -constructible graphs solely through -critical graphs were found for all. For, one such example is the graph obtained from the dodecahedron graph by adding a new edge between each pair of antipodal vertices
The Hajós number
Because merging two non-adjacent vertices reduces the number of vertices in the resulting graph, the number of operations needed to represent a given graph using the operations defined by Hajós may exceed the number of vertices in. 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. However, it is not known how to prove non-polynomial lower bounds on the Hajós number without making some complexity-theoretic assumption, and if such a bound could be proven it would also imply the existence of non-polynomial bounds on certain types of Frege system in mathematical logic. The minimum size of an expression tree describing a Hajós construction for a given graph may be significantly larger than the Hajós number of, because a shortest expression for may re-use the same graphs multiple times, an economy not permitted in an expression tree. There exist 3-chromatic graphs for which the smallest such expression tree has exponential size.
Other applications
used the Hajós construction to generate an infinite set of 4-critical polyhedral graphs, each having more than twice as many edges as vertices. Similarly, used the construction, starting with the Grötzsch graph, to generate many 4-critical triangle-free graphs, which they showed to be difficult to color using traditional backtracking algorithms. In polyhedral combinatorics, used the Hajós construction to generate facets of the stable setpolytope.
