Let $G$ be a connected graph with $m$ edges. Prove that the edges can be labelled with the positive integers $1,2,…,m$ such that for each vertex with degree at least two, the greatest common divisors amongst the labels on the edges incident to this vertex, is $1$.
One way to achieve that is by ensuring that all vertices have atleast two edges with consecutive labels. But I am not sure if this is always possible.
I found a way to do this whenever the graph has a hamiltonian path or a eulerian circuit. But I could not prove anything in general.