Q8 Matemática  (Tuymaada 2016)

Um grafo conectado é dado. Prove que seus vértices podem ser coloridos de azul e verde e algumas de suas arestas marcadas de modo que cada dois vértices sejam conectados por um caminho de arestas marcadas, cada aresta marcada conecte dois vértices de cores diferentes e não haja dois vértices verdes conectados por uma aresta de o gráfico original.