Question

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?

Answer 1

Notation: αβ means apply α then β.

If the graph is not a tree, then either it contains a cycle or it contains less than n−1 edges. In the latter case, we get a contradiction since less than n−1 transpositions cannot multiply to a big cycle.

So suppose that the graph contains a cycle (12...k), and assume that for each order of the edges, you get a big cycle. In particular, this holds for orderings where you take the cycle last. Fix some ordering of the other edges, and denote the interim product (without the edges of the cycle) by π. So for each product σ of the edges of the cycle, πσ is a long cycle.

For each i<j, there is some ordering of the cycle which produces a permutation containing the transposition (ij). Indeed, take (i i+1)(i+1 i+2)...(j-2 j-1) (j j+1) ... (k 1) (1 2) ... (i-1 i) (j-1 j).

Thus for each i<j, π(ij)τ is a big cycle, where τ does not involve i or j. In particular, π(i)≠j. Since this is true for all i≠j, it follows that π must be the identity. We get a contradiction since σ is not a big cycle.