1991 IMO Problems/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.

Solution

We provide an algorithmic approach for labelling the edges: We start off with the set $V$ of all vertices in $G$ . For each step in the process we remove a number of vertices from the set $V$ if their exists an edge sorrounding it which is labelled. Additionally, we shall use up the numbers $1,2,...,k$ in the order from least to greatest.

Here is the process: Let $u$ be the least number not used yet. Take the longest path that uses any vertex once formed solely by vertices from $V$ and call it path $P=(v_1,v_2,...,v_n)$ . If $v_1$ has more than one edge, then since $P$ is maximal, it must be connected to some other edge $v_0$ which could be one of the vertices $v_i$ or one of the vertices not in $V$ . Similarly, if $v_n$ has more than one edge, it must be connected to a vertex $v_{n+1}$ which is either one of the $v_i$ or one of the vertices not in $V$ . Notice that since $v_1,v_n\in V$ the edge connecting $v_0$ and $v_1$ and the edge connecting $v_n$ and $v_{n+1}$ are not labelled. Now, if $v_0$ exists, we shall label the edge joining $v_i$ and $v_{i+1}$ with the number $u+i$ . If $v_0$ does not exist then we shall label the edge joining $v_i$ and $v_{i+1}$ with the number $u+i-1$ .

If $v_0$ or $v_{n+1}$ 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 $V$ , the edges $v_1,v_2,...,v_n$ are removed from $V$ . Thus, it is clear that all vertices not in $V$ , at any time, have edges sorrounding them that are relatively prime.

We repeat the process described until the only vertices in $V$ are those which are not connected to any other vertices in $V$ . Let the least number we have not yet used by $u$ . If any of them are of degree 1, we do not care. If there is a vertex $v$ of degree at least 2, then we simply label 2 of its edges $u$ and $u+1$ and now its edges are relatively prime, and we can remove it from $V$ . Notice that this doesn't remove any other vertices from $V$ since $v$ is not connected to any vertices from $V$ . We continue like this for the other vertices in $V$ .

Now, all the vertices in $V$ are those whose edges do not matter, while all vertices not in $V$ are those with edges relatively prime. Thus we have the desired configuration, and we simply distribute the remaining numbers in any way we wish.

Page

Toolbox

Search

1991 IMO Problems/Problem 4

Solution