IMO 1991 SL 10

Origin: USA

Problem

Suppose G is a connected graph with n edges. Prove that it is possible to label the edges of G from 1 to n in such a way that in every vertex v of G with two or more incident edges, the set of numbers labeling those edges has no common divisor greater than 1.

Solution

We start at some vertex v0 and walk along distinct edges of the graph, numbering them 1, 2, . . . in the order of appearance, until this is no longer possible without reusing an edge. If there are still edges which are not numbered, one of them has a vertex which has already been visited (else G would not be connected). Starting from this vertex, we continue to walk along unused edges resuming the numbering, until we eventually get stuck. Repeating this procedure as long as possible, we shall number all the edges. Let v be a vertex which is incident with e \geq2 edges. If v = v0, then it is on the edge 1, so the gcd at v is 1. If v ̸= v0, suppose that it was reached for the first time by the edge r. At that time there was at least one unused edge incident with v (as e \geq2), hence one of them was labelled by r + 1. The gcd at v again equals gcd(r, r + 1) = 1.