1991 IMO Problems/Problem 4
Suppose is a connected graph with edges. Prove that it is possible to label the edges 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.
We provide an algorithmic approach for labelling the edges: We start off with the set of all vertices in . For each step in the process we remove a number of vertices from the set if their exists an edge sorrounding it which is labelled. Additionally, we shall use up the numbers in the order from least to greatest.
Here is the process: Let be the least number not used yet. Take the longest path that uses any vertex once formed solely by vertices from and call it path . If has more than one edge, then since is maximal, it must be connected to some other edge which could be one of the vertices or one of the vertices not in . Similarly, if has more than one edge, it must be connected to a vertex which is either one of the or one of the vertices not in . Notice that since the edge connecting and and the edge connecting and are not labelled. Now, if exists, we shall label the edge joining and with the number . If does not exist then we shall label the edge joining and with the number .
If or does not exist, then the vertex they should have been connected to has degree 1, and so the labels of the edges sorrounding it do not matter. Otherwise and the case of any other vertex in the path, our process garuntees that the vertex will be sorrounded by two edges labelled by 2 consecutive numbers. Thus, that vertex will be sorrounded by edges whose greates common factor is 1, no matter how the other edges sorrounding it are labelled. Notice that from our definition of , the edges are removed from . Thus, it is clear that all vertices not in , at any time, have edges sorrounding them that are relatively prime.
We repeat the process described until the only vertices in are those which are not connected to any other vertices in . Let the least number we have not yet used by . If any of them are of degree 1, we do not care. If there is a vertex of degree at least 2, then we simply label 2 of its edges and and now its edges are relatively prime, and we can remove it from . Notice that this doesn't remove any other vertices from since is not connected to any vertices from . We continue like this for the other vertices in .
Now, all the vertices in are those whose edges do not matter, while all vertices not in are those with edges relatively prime. Thus we have the desired configuration, and we simply distribute the remaining numbers in any way we wish.