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 3 of 4: Handle the first endpoint

Previous step Next step

\gcd\{\text{labels at }A\}=1\quad\text{or}\quad\deg(A)=1

Detailed analysis

For the first path, give its first edge label 1. Hence its start vertex A has gcd 1 if it has at least two incident edges. If it has only one edge, the condition does not apply. The endpoint B is either a leaf, or it was already an internal/previously treated vertex and is safe.