Hajós construction¶

A graph-composition operation that deletes one edge from each of two graphs, identifies selected endpoints and joins the remaining endpoints.

Version: v2 · 2026-09-19 · History
Domain-specific #: 4806
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Graph Theory → Mathematics
Aliases: Hajós sum

Core Idea¶

Endpoint choice matters for nonsymmetric inputs, simple-graph conventions can require cleanup and the broader Hajós constructibility theorem also permits vertex identification and supergraphs. Two edge-bearing graphs are spliced by removing chosen edges, merging one endpoint pair and adding a cross-edge, a transformation that preserves a lower bound on chromatic number and generates critical color structures. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Snip, Glue, and Tie

Imagine coloring dots so that any two dots joined by a line get different colors. Take two dot-drawings that each need lots of colors, snip one line in each, glue one end from each drawing together, and tie the other two loose ends with a new line. The new drawing still needs at least as many colors as before.

The Color-Keeping Graph Splice

In graph coloring, you color dots so that any two dots joined by a line get different colors. The Hajós construction combines two graphs: pick a line in each, remove both lines, merge one end of the first line with one end of the second into a single dot, and then add a new line between the two other ends. The surprising part is that if both graphs needed at least k colors, the new one does too. Which ends you choose to merge matters. Mathematicians use this move to build graphs that are tricky to color.

Chromatic-Bound-Preserving Graph Join

The Hajós construction joins two undirected graphs G and H. Choose an edge xy in G and an edge uv in H, with a declared choice of which endpoints to use. Delete both edges, identify x with u into a single vertex, and add a new edge joining y and v. If G and H each have chromatic number at least k, the result also has chromatic number at least k, so the move preserves this lower bound and is used to generate 'critical' graphs that need many colors. The choice of endpoints can change the result, and when working with simple graphs you may need to clean up loops or duplicate edges. A broader theorem on Hajós constructibility also allows merging nonadjacent vertices and adding edges or vertices.

Given undirected graphs G and H with chosen oriented edges (x, y) in G and (u, v) in H, the Hajós construction deletes xy and uv, identifies x with u, and adds the cross-edge yv. The key invariant: if χ(G) ≥ k and χ(H) ≥ k, then the Hajós sum also has chromatic number at least k, since any (k−1)-coloring would induce colorings forcing a contradiction at the merged vertex and the cross-edge. The operation also preserves k-criticality, so it generates families of critical color structures. Endpoint orientation matters when the inputs are not symmetric, and in the simple-graph convention one may need to clean up loops or multiple edges that arise. The construction should be distinguished from the broader Hajós constructibility theorem, which additionally allows identifying non-adjacent vertices and passing to supergraphs, and which characterizes graphs of chromatic number at least k as those obtainable from K_k. A correct application states the inputs, endpoint choices, deletions, identification, added edge, and multigraph conventions explicitly.

Scope of Application¶

Hajós construction belongs to graph theory and is useful where the analyst can specify the typed graph theory carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, then evaluate the two undirected input graphs, selected oriented endpoint pairs, deletion of both edges, identified vertices, added cross-edge, treatment of loops and multiple edges, resulting graph and chromatic-number and constructibility consequences are explicit. The scope is broad within that domain but bounded by the need for the two undirected input graphs, selected oriented endpoint pairs, deletion of both edges, identified vertices, added cross-edge, treatment of loops and multiple edges, resulting graph and chromatic-number and constructibility consequences are explicit.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the two undirected input graphs, selected oriented endpoint pairs, deletion of both edges, identified vertices, added cross-edge, treatment of loops and multiple edges, resulting graph and chromatic-number and constructibility consequences are explicit the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Hajós construction. Hajós construction compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed graph theory carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the two undirected input graphs, selected oriented endpoint pairs, deletion of both edges, identified vertices, added cross-edge, treatment of loops and multiple edges, resulting graph and chromatic-number and constructibility consequences are explicit independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of graph theory because they reuse the typed graph theory carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, Two edge-bearing graphs are spliced by removing chosen edges, merging one endpoint pair and adding a cross-edge, a transformation that preserves a lower bound on chromatic number and generates critical color structures., and type the carrier, state every parameter and convention in the definition, test that the two undirected input graphs, selected oriented endpoint pairs, deletion of both edges, identified vertices, added cross-edge, treatment of loops and multiple edges, resulting graph and chromatic-number and constructibility consequences are explicit, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Hajós construction Domain-specific

Parents (1) — outgoing typed relations

Hajós construction is a kind of Composition Prime

It remains its own entry because its identity is fixed by the two undirected input graphs, selected oriented endpoint pairs, deletion of both edges, identified vertices, added cross-edge, treatment of loops and multiple edges, resulting graph and chromatic-number and constructibility consequences.

Hierarchy path (1) — routes to 1 parentless root

Hajós construction → is a kind of Composition → presupposes Gestalt Principles → is a decomposition of Holism

Neighborhood in Abstraction Space¶

Hajós construction sits in a crowded region of the domain-specific corpus (3^rd percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Graph Theory Structures & Invariants (48 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25