IMO 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$.

=============================

Proof:

We show a stronger result, that every vertex of degree more than $1$ is incident to two consecutive integers except possibly a vertex incident to both $k$ and $1$. If $G$ has a vertex $v_1$ of degree $1$, then we remove the path $(v_1,v_2,\dots,v_m)$ from $G$ to obtain $G'$ where $\deg_G(v_2)=\deg_G(v_3)=\dots=\deg_G(v_m)=2$ and the neighbor of $v_m$ in $G'$ has degree at least $2$ in $G'$. By induction on $k$ we can first label $E(G')$, then label edges $v_1v_2,v_2v_3,\dots$ sequentially.

If every vertex of $G$ has degree at least $2$, then we pair and connect the vertices of odd degrees to obtain $G''$, which has an  Eulerian circuit $C$. We go through trails in $C$ composed of $E(G)$ and label the edges from $1$ to $k$. If a vertex $v$ has odd degree than it is at least $3$, and at least two of the edges incident to $v$ are labeled with consecutive integers.