Suppose a simple graph has $n$ vertices and $m$ edges. If the vertices are labelled, then each edge then corresponds to a transposition in a natural way. A theorem in Godsil and Royle's Algebraic Graph Theory, section 3.10, asserts the following:

If the graph is not a tree, then some product of the $m$ distinct transpositions is not an $n$-cycle.

For example, consider $K_4-e$, i.e. the graph with vertex set $\[4\]$ and edges $\lbrace 1, 2\rbrace, \lbrace 1, 3\rbrace, \lbrace1, 4\rbrace, \lbrace 2, 3\rbrace$, and $\lbrace2, 4\rbrace$. Then $(1 2)(1 4)(1 3)(2 4)(2 3) = (1 4 2 3)$, a 4-cycle. However, $(1 2)(1 4)(1 3)(2 3)(2 4) = (1 3).$

Unfortunately for me, the proof is left as an exercise, which I cannot solve. Can anyone help?