Se nos dan $k$ colores y tenemos que asignar un solo color a cada vértice. Un borde se satisface si los vértices en ese borde son de diferentes colores. Pruebe que siempre puede encontrar un algoritmo que asigne colores a los vértices de modo que al menos $\frac{k - 1}{k}|E|$ bordes estén satisfechos donde $\(|E|\)$ es la cardinalidad de los bordes en el grafo. Pruebe que existe un algoritmo determinista de tiempo polinómico para esto.