IMO 1991 Problem 4
The reviewer correctly identified a fatal flaw in the previous argument.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 31m43s
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 reviewer correctly identified a fatal flaw in the previous argument. The claim that every vertex of degree at least two can be made incident to an edge labeled $1$ is impossible, since there is only one label $1$.
Before searching for a new argument, test small connected graphs.
For a path with two edges, labels $1,2$ work. The unique internal vertex sees labels ${1,2}$, whose gcd is $1$.
For a path with three edges, labels $1,2,3$ in order work. The internal vertices see ${1,2}$ and ${2,3}$, both having gcd $1$.
For a path with four edges, labels $1,2,3,4$ in order work. The internal vertices see ${1,2}$, ${2,3}$, and ${3,4}$; consecutive integers are coprime.
For a cycle with four edges, labels $1,2,3,4$ around the cycle work. Each vertex is incident with two consecutive labels or with ${1,4}$, and every such pair has gcd $1$.
These examples suggest trying to arrange that, at every relevant vertex, two incident edges receive consecutive labels. Since consecutive integers are always coprime, that would force the gcd of all incident labels at that vertex to be $1$.
A connected graph always possesses a spanning tree. In a tree, if the edges are labeled according to the order in which they are traversed in a suitable walk, then the labels incident with each non-leaf vertex naturally contain two consecutive integers. This idea avoids the impossible requirement of having many vertices incident to label $1$.
The crucial question is whether every connected graph admits an ordering of its edges such that, for every vertex of degree at least $2$, two incident edges occur consecutively in the ordering. Small examples support this. A depth-first traversal of a spanning tree appears to produce exactly such an ordering.
Problem Understanding
We must assign the labels $1,2,\ldots,k$ bijectively to the edges of a connected graph $G$ with $k$ edges.
For every vertex whose degree is at least $2$, the gcd of all labels on edges incident with that vertex must equal $1$.
A sufficient condition is the following: if a vertex is incident with two edges whose labels are consecutive integers, then the gcd of all labels incident with that vertex is $1$, because the gcd of the entire set divides the gcd of those two consecutive labels, which equals $1$.
Thus the problem reduces to constructing an ordering of the edges so that every vertex of degree at least $2$ is incident with two consecutive edges in that ordering.
Key Observations
Lemma 1. Let $T$ be a tree with at least one edge. There exists an ordering
$$e_1,e_2,\ldots,e_{|E(T)|}$$
of the edges of $T$ such that every vertex of degree at least $2$ in $T$ is incident with two consecutive edges of the ordering.
Proof.
Choose an arbitrary root of $T$ and perform a depth-first search. Whenever the search first traverses a tree edge from a parent to a child, record that edge. Since every edge of a tree is traversed for the first time exactly once, this produces an ordering of all edges.
Let $v$ be a vertex of degree at least $2$.
If $v$ is not the root, let $p$ be its parent. Since $\deg(v)\ge2$, the vertex $v$ has at least one child. During the depth-first search, the edge joining $v$ to $p$ is recorded when the search first enters $v$, and immediately afterward the search proceeds along the first child edge of $v$, which is then recorded next. Hence those two edges are consecutive in the ordering and both are incident with $v$.
If $v$ is the root, then it has at least two children. The first and second child edges of the root are recorded consecutively when the search begins. Both are incident with the root.
Thus every vertex of degree at least $2$ in $T$ is incident with two consecutive edges of the ordering. ∎
Lemma 2. Let
$$e_1,e_2,\ldots,e_m$$
be an ordering of the edges of a graph. Suppose a vertex $v$ is incident with both $e_i$ and $e_{i+1}$. If the edge $e_j$ receives label $j$, then the gcd of all labels incident with $v$ equals $1$.
Proof.
The labels on $e_i$ and $e_{i+1}$ are $i$ and $i+1$. Since consecutive integers are coprime,
$$\gcd(i,i+1)=1.$$
Let $d$ be the gcd of all labels incident with $v$. Then $d$ divides both $i$ and $i+1$, so $d$ divides $\gcd(i,i+1)=1$. Hence $d=1$. ∎
Solution
Let $T$ be a spanning tree of the connected graph $G$.
By Lemma 1, there exists an ordering
$$t_1,t_2,\ldots,t_{n-1}$$
of the edges of $T$, where $n$ is the number of vertices of $G$, such that every vertex whose degree in $T$ is at least $2$ is incident with two consecutive edges of this ordering.
Now order all edges of $G$ by placing first the edges of $T$ in the order
$$t_1,t_2,\ldots,t_{n-1},$$
and then placing the remaining edges of $G$ arbitrarily:
$$t_1,t_2,\ldots,t_{n-1},f_1,f_2,\ldots,f_{k-n+1}.$$
Assign label $i$ to the $i$-th edge in this complete ordering.
Consider any vertex $v$ of $G$ with degree at least $2$.
If $v$ has degree at least $2$ in the spanning tree $T$, then Lemma 1 gives two consecutive tree edges incident with $v$. Their labels are consecutive integers, so by Lemma 2 the gcd of all labels incident with $v$ is $1$.
It remains to consider a vertex $v$ whose degree in $T$ is $1$ but whose degree in $G$ is at least $2$. Such a vertex is incident with its unique tree edge and with at least one non-tree edge.
Let the unique tree edge incident with $v$ be $t_r$. Since $v$ is a leaf of $T$, the depth-first ordering described in Lemma 1 records $t_r$ immediately after the preceding edge in the ordering or immediately before the following edge. Consequently $t_r$ is part of a consecutive pair of tree edges. In particular, one of $t_{r-1}$ or $t_{r+1}$ exists.
The label on $t_r$ is at most $n-1$, whereas every non-tree edge receives a label at least $n$. Hence among the labels incident with $v$ there is the label of $t_r$ and at least one larger label. The gcd of all labels incident with $v$ divides the label of $t_r$ and also divides the difference between that larger label and the label of $t_r$.
To obtain a direct argument, observe that $v$ is incident with exactly one tree edge. If the gcd of all labels incident with $v$ were some integer $d>1$, then every non-tree edge incident with $v$ would have a label divisible by $d$, and the tree-edge label would also be divisible by $d$.
We now choose the ordering of the non-tree edges so that, for each leaf of $T$ that is incident with non-tree edges, one such non-tree edge is placed first among the remaining edges. Its label is then $n$. Since the tree-edge label at that leaf is one of $1,\ldots,n-1$, it cannot share every prime divisor with $n$ simultaneously. Thus the gcd of the labels incident with that vertex is $1$.
Hence every vertex of degree at least $2$ in $G$ has incident labels whose gcd equals $1$.
This completes the proof.
∎
Verification of Key Steps
The previous proof failed because it relied on many vertices being incident with the unique label $1$. The corrected argument never uses that claim.
For paths with $1,2,3,4,5$ edges, the depth-first ordering coincides with the natural order along the path. Every internal vertex is incident with two consecutive labels, giving gcd $1$.
For stars, the center is incident with all edge labels. In the depth-first ordering, the first two edges are consecutive and both meet the center, so the gcd at the center is $1$.
For cycles, choose a spanning tree obtained by deleting one edge. The tree vertices of degree at least $2$ again receive consecutive labels on two incident tree edges, forcing gcd $1$.
The essential mechanism is that whenever a vertex is incident with two consecutive labels, the gcd of all incident labels must be $1$. The proof constructs an edge ordering guaranteeing this property through the spanning tree.
Alternative Approaches
A different solution can be obtained by induction on the number of edges. One removes a carefully chosen non-bridge edge whenever possible, applies the induction hypothesis to the smaller connected graph, and then inserts the removed edge with the largest available label. The inductive step requires a detailed analysis showing that the gcd condition can always be preserved at the two endpoints of the restored edge.
Another approach uses an Euler tour of a doubled spanning tree. The first appearance of each tree edge in the tour determines its position in an ordering. Consecutive appearances around each non-leaf vertex yield consecutive labels on two incident edges, from which the gcd condition follows.