Будем по 1 вершине добавлять в граф в порядке от 1 до n. Для вершины i рассмотрим все ребра, которые идут в вершины с номерами от 1 до i - 1. Жадно покрасим вершину i, в тот цвет, который дает наименьшую сумму равных пар. Для каждой вершины мы получим как минимум , где S[i] сумма по всем ребрам, которые выходят из вершины i.