International Mathematical Olympiad 1991 Problem 4

Suppose $G$ is a connected graph with $k$ edges. Prove that it is possible to label the edges $1, 2, \ldots, k$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1.

[A graph consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $u, v$ belongs to at most one edge. The graph $G$ is connected if for each pair of distinct vertices $x, y$ there is some sequence of vertices $x = v_0, v_1, v_2, \ldots, v_m = y$ such that each pair $v_i, v_{i+1}$ ($0 \leq i < m$) is joined by an edge of $G$.]