Q4 Matemática  (IMO 1991)

Suponha que $G$ seja um grafo conexo com $k$ arestas. Prove que é possível rotular as arestas $1,2,\dots ,k$ de tal forma que em cada vértice que pertence a duas ou mais arestas, o máximo divisor comum dos inteiros que rotulam essas arestas é igual a 1. Nota: Definição de Gráfico. Um grafo consiste em um conjunto de pontos, chamados vértices, juntamente com um conjunto de arestas que unem certos pares de vértices distintos. Cada par de vértices $u,v$ pertence a no máximo uma aresta. O grafo $G$ é conexo se para cada par de vértices distintos $x,y$ existe alguma sequência de vértices $x=v_0,v_1,v_2,cdots,v_m=y$ tal que cada par $v_i,v_{i+1}(0\le i<m)$ é unido por uma aresta de $,G$.