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 1.

Step 2 of 4: Label each maximal unlabeled path consecutively

Previous step Next step

e_1,e_2,\ldots,e_s\quad\mapsto\quad q,q+1,\ldots,q+s-1

Detailed analysis

Start at a vertex A and follow a path through unlabeled edges until reaching an endpoint B with no unlabeled edge left. Give the traversed edges the next consecutive unused labels. Every internal vertex on the path is incident with two consecutive labels and is therefore safe.