Suppose G is a connected graph with k edges. Prove that it is possible to label the edges 1,2,…,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.
Sign in to check your answer and unlock the solution.