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 4 of 4: Repeat at the boundary of the labeled region
Detailed analysis
If unlabeled edges remain, connectedness provides a boundary vertex C incident with both a labeled and an unlabeled edge. Start the next maximal unlabeled path at C and continue with the next unused consecutive labels. C already satisfies the invariant, all new internal vertices are safe by the consecutive-label observation, and the endpoint is safe by the same leaf-or-treated argument. Repeating terminates after all k edges are labeled.