Problem 4
Suppose G is a connected graph with k 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 1.
Step 1 of 4: Use the coprimality of consecutive labels
Detailed analysis
The key observation is that any two consecutive positive integers have gcd 1. Thus a vertex incident with two edges carrying consecutive labels automatically satisfies the required condition, regardless of its other incident labels.