Q3 Matemática  (Silk Road 2008)

Seja $G$ um grafo com $2n$ vértices e $2n(n-1)$ arestas. Se colorirmos alguma aresta de vermelho, então os vértices, que estão conectados por essa aresta, também devem ser coloridos de vermelho. Mas não é necessário que todas as arestas do vértice vermelho sejam vermelhas. Prove que é possível colorir alguns vértices e arestas em $G$, de modo que todos os vértices vermelhos tenham exatamente $n$ arestas vermelhas.