χ(G) ≤ Δ(G) + 1.
El número cromático de una gráfica $G$, que escribes como $\chi(G)$, es la cantidad mínima de colores que necesitas para colorear los vértices de $G$ de tal forma que no haya dos vértices adyacentes con el mismo color. Determinar el valor exacto de $\chi(G)$ es computacionalmente difícil (NP-duro) para gráficas en general. Por eso, encontrar cotas para $\chi(G)$ basadas en invariantes de la gráfica que sean fáciles de calcular es un problema fundamental en combinatoria. La cota superior más común relaciona el número cromático con el grado máximo de la gráfica, que denotas como $\Delta(G)$.
La desigualdad fundamental $\chi(G) \leq \Delta(G) + 1$ asegura que siempre puedes colorear una gráfica usando, a lo mucho, un color más que el número máximo de aristas conectadas a cualquier vértice. La intuición detrás de esta cota parte de un enfoque "voraz" (o greedy): si coloreas los vértices uno por uno, el peor escenario para cualquier vértice es que a todos sus vecinos ya les hayan asignado colores diferentes. Como un vértice tiene máximo $\Delta(G)$ vecinos, hay a lo mucho $\Delta(G)$ colores "prohibidos". Por lo tanto, si tienes una paleta de $\Delta(G) + 1$ colores, siempre habrá al menos un color disponible para el vértice actual.
Aunque esta cota siempre se