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.
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.
For example, let G and H each be a complete graph K4 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 G and H are cycle graphs of length p and q respectively, then the result of applying the Hajós construction is itself a cycle graph, of length p + q − 1.
...
Wikipedia