Олимпиада Туймаада по математике. Старшая лига. 2013 год

Вершины связного графа нельзя покрасить меньше чем в $n+1$ цвет так, чтобы соседние вершины были разного цвета. Докажите, что можно удалить из графа $n(n-1)/2$ ребер без потери связности. ( В. Дольников )