IMO 1991 Problem 4

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 8m29s

Problem

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.

Exploration

The earlier attempt failed because it tried to control gcd conditions via prime avoidance without a stable invariant. The correct reformulation is that a vertex of degree at least $2$ must have incident labels not all sharing a common prime factor. A sufficient stronger condition is that each such vertex contains two incident edges whose labels are coprime. A still stronger and easier-to-force condition is that some vertex contains two incident edges whose labels are consecutive integers, since consecutive integers are always coprime.

Testing small graphs confirms feasibility. For a single edge there is no condition. For a path of length $2$ or $3$, assigning consecutive integers along the path immediately produces a vertex with consecutive incident labels. For a star with $k$ edges, ordering edges arbitrarily already allows consecutive labels at the center, so the requirement is easily satisfied. These checks indicate that forcing a local consecutive pair at every branching vertex is a viable strategy.

The key difficulty is ensuring that this can be achieved simultaneously for all vertices in an arbitrary connected graph while still using each label exactly once.

Problem Understanding

A connected graph $G$ with $k$ edges must have its edges bijectively labeled by $1,2,\dots,k$ so that for every vertex of degree at least $2$, the greatest common divisor of the labels on edges incident to that vertex equals $1$.

This condition is equivalent to requiring that no vertex has all incident labels divisible by any fixed prime. A sufficient condition is that each such vertex has at least one pair of incident edges whose labels are coprime.

The task is therefore to construct a global labeling that enforces a local coprimality witness at every vertex.

Key Observations

If a vertex has two incident edges labeled with consecutive integers, then the gcd of all incident labels at that vertex is $1$, since consecutive integers are coprime.

A spanning tree structure allows every vertex except the root to have a distinguished parent edge. If one can ensure that at each non-root branching vertex the parent edge and the first processed child edge receive consecutive labels, then every vertex of degree at least $2$ will contain a coprime pair.

A depth-first traversal allows edges to be exposed in a controlled order where each tree edge is first encountered exactly once from the parent side, enabling deterministic assignment of labels.

Solution

Fix a spanning tree $T$ of $G$ rooted at an arbitrary vertex $r$. Perform a depth-first search on $T$. Maintain a counter $t$ initially equal to $1$.

Each tree edge $e=uv$ is assigned a label at the moment it is first traversed from the parent endpoint to the child endpoint in the DFS. At that moment, assign the current value of $t$ to $e$ and then increase $t$ by $1$.

After finishing the traversal of all tree edges, assign the remaining edges of $G$ (those not in $T$) arbitrarily with the remaining unused integers in any order, increasing $t$ consecutively.

This produces a bijective labeling of all edges with $1,2,\dots,k$.

Now consider a vertex $v$ of degree at least $2$.

If $v$ is not the root, let $e_p$ be its parent edge in the DFS tree. When the DFS first arrives at $v$ through $e_p$, the edge $e_p$ is labeled with some integer $a$. Immediately after entering $v$, the DFS begins processing the first child edge $e_c$ of $v$ (if it exists), and this edge receives the next label $a+1$.

Thus, whenever $v$ has degree at least $2$ in the tree, it contains two incident edges labeled $a$ and $a+1$, which are consecutive integers and therefore coprime. Hence the gcd of all incident labels at $v$ is $1$.

If $v$ has additional incident edges not in the tree, these receive labels that do not affect the conclusion, since adding elements to a set cannot increase its greatest common divisor.

If $v$ is the root and has at least two incident tree edges, then the first two edges processed at $v$ in the DFS receive consecutive labels by the same mechanism, again producing a coprime pair.

Therefore every vertex of degree at least $2$ has incident edges whose labels have greatest common divisor equal to $1$.

This completes the construction.

∎

Verification of Key Steps

The labeling is a bijection because each edge of the spanning tree is assigned exactly once upon its first traversal in DFS, and each non-tree edge is assigned exactly once afterward using the remaining unused integers.

At every non-leaf vertex of the DFS tree, the parent edge and the first child edge are assigned consecutive integers because the counter increases by exactly one between successive edge assignments at that moment. Since consecutive integers are always coprime, this guarantees a coprime pair at every vertex of degree at least $2$ in the tree.

Adding additional incident edges cannot destroy the property because the gcd of a set divides the gcd of every subset, so once a subset has gcd $1$, the full set also has gcd $1$.

Alternative Approaches

An alternative method is to construct an Euler tour of the spanning tree and label edges in traversal order, then adjust the argument to guarantee that each vertex receives at least one pair of incident edges with relatively prime labels. Another approach is to orient the tree and assign labels along directed paths so that each vertex inherits a consecutive pair from the entry and exit of its DFS interval.