Q3 Matemática  (Tuymaada 2013)

Os vértices de um grafo conexo não podem ser coloridos com menos de $n+1$ cores (para que os vértices adjacentes tenham cores diferentes). Prove que $\frac{n(n-1)}{2}$ arestas podem ser removidas do grafo para que ele permaneça conectado. V. Dolnikov EDIT. É confirmado pela solução oficial que o grafo é tacitamente assumido como finito.