ein Verfahren, um jeden GraphenG, der für k ∈ ℕ eine chromatische Zahl χ(G) ≥ k besitzt, schrittweise aus einem vollständigen Graphen K_k zu gewinnen.

Im folgenden bezeichne Ω_k die Klasse aller Graphen G mit _χ(G) ≥ k. Einer Idee G. Hajós (1961) folgend, erhält man mittels der beiden unten angeführten Operationen aus Graphen, die in Ω_k liegen, neue Graphen, die wieder zu Ω_k gehören.

1. (1.) Durch Identifikation zweier nicht adjazenter Ecken eines Graphen aus Ω_k.
2. (2.) Sind G und G′ zwei disjunkte Graphen aus der Klasse Ωk und uv ∈ K(G) sowie u′V′ ∈ K(G′), so erhält man die sogenannte Hajós-Vereinigung der beiden Graphen G und G′ wie folgt: Man entferne die beiden Kanten uv und u′v′, identifiziere u mit u′ und füge danach die neue Kante vv′ hinzu.

Ein Graph G heißt k-konstruierbar, wenn man ihn, ausgehend von dem vollständigen Graphen K_k, durch wiederholtes Anwenden von (1.) und (2.) erzeugen kann.

Wie man leicht sieht, sind alle k-konstruierbaren Graphen, und damit auch deren Obergraphen, mindestens k-chromatisch. Bemerkenswert ist, daß Hajós 1961 auch die Umkehrung beweisen konnte.

Jeder Graph G aus Ω_k enthält einen k-konstruierbaren Teilgraphen.