Hajós construction
In graph theory, a branch of mathematics, the Hajós construction is an operation on graphs named after György Hajós (1961) that may be used to construct any critical graph or any graph whose chromatic number is at least some given threshold. == The construction == Let G and H be two undirected graphs, vw be an edge of G, and xy be an edge of H. Then the Hajós construction forms a new graph that combines the two graphs by identifying vertices v and x into a single vertex, removing the two edges vw and xy, and adding a new edge wy.