Hajós construction

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.

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.

There exist 3-chromatic graphs for which the smallest such expression tree has exponential size.

[8] Koester (1991) 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.

In polyhedral combinatorics, Euler (2003) used the Hajós construction to generate facets of the stable set polytope.

Applying the Hajós construction to two copies of K 4 by identifying a vertex from each copy into a single vertex (shown with both colors), deleting an edge incident to the combined vertex within each subgraph (dashed) and adding a new edge connecting the endpoints of the deleted edges (thick green), produces the Moser spindle .