Suppose G is a connected graph with k edges. Prove that it is possible to label the edges 1, 2, ... , 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 1.
[A graph is a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of edges belongs to at most one edge. The graph is connected if for each pair of distinct vertices x, y there is some sequence of vertices x = v0, v1, ... , vm = y, such that each pair vi, vi+1 (0 ≤ i < m) is joined by an edge.]
Solution
The basic idea is that consecutive numbers are relatively prime.
We construct a labeling as follows. Pick any vertex A and take a path from A along unlabeled edges. Label the edges consecutively 1, 2, 3, ... as the path is constructed. Continue the path until it reaches a vertex with no unlabeled edges. Let B be the endpoint of the path. A is now guaranteed to have the gcd (= greatest common divisor) of its edges 1, because one of its edges is labeled 1. All the vertices between A and B are guaranteed to have gcd 1 because they have at least one pair of edges with consecutive numbers. Finally, either B has only one edge, in which case its gcd does not matter, or it is also one of the vertices between A and B, in which case its gcd is 1.
Now take any vertex C with an unlabeled edge and repeat the process. The same argument shows that all the new vertices on the new path have gcd 1. The endpoint is fine, because either it has only one edge (in which case its gcd does not matter) or it has already got gcd 1.
Repeat until all the edges are labeled.
Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
19 Nov 1998