Шелковый путь олимпиада по математике 2008 года | Казахстанские олимпиады

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