# characterization of trees in terms of products of transpositions

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?

-

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.

-
You should add the easy case of a non-connected graph. –  Benoît Kloeckner Jul 20 '10 at 7:39
If the graph is not connected, then either there are less than n-1 edges or there's a cycle. Less than n-1 transpositions cannot multiply to a big cycle. –  Yuval Filmus Jul 20 '10 at 15:54
I do not follow your fourth paragraph. Consider the graph with edges $(51)(53)(54)(52)(12)(23)(41)(34)$. It contains a cycle on $\lbrace 1, 2, 3, 4 \rbrace$. In your notation, let $\pi = (51)(53)(54)(52) = (51342)$. Let $i=1$ and $j=4$. Then $\sigma = (12)(23)(41)(34)$ which does indeed equal $(14)(23)$. Thus $\tau = (2 3)$, which does not contain 1 or 4. However $\pi (i j) \tau = (1 2 5 4 3)$, a big cycle. Yet 1 and 4 are in the same cycle of $\pi$. –  user7760 Jul 20 '10 at 21:30
I modified the proof, hopefully now it does work. –  Yuval Filmus Jul 20 '10 at 22:16