characterization of trees in terms of products of transpositions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T22:34:53Z http://mathoverflow.net/feeds/question/32552 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32552/characterization-of-trees-in-terms-of-products-of-transpositions characterization of trees in terms of products of transpositions alumbros 2010-07-19T22:56:01Z 2010-08-13T15:08:56Z <p>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:</p> <p>If the graph is not a tree, then some product of the \$m\$ distinct transpositions is not an \$n\$-cycle.</p> <p>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).\$</p> <p>Unfortunately for me, the proof is left as an exercise, which I cannot solve. Can anyone help?</p> http://mathoverflow.net/questions/32552/characterization-of-trees-in-terms-of-products-of-transpositions/32578#32578 Answer by Yuval Filmus for characterization of trees in terms of products of transpositions Yuval Filmus 2010-07-20T02:35:29Z 2010-08-13T15:08:56Z <p>Notation: &alpha;&beta; means apply &alpha; then &beta;.</p> <p>If the graph is not a tree, then either it contains a cycle or it contains less than n&minus;1 edges. In the latter case, we get a contradiction since less than n&minus;1 transpositions cannot multiply to a big cycle.</p> <p>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 &pi;. So for each product &sigma; of the edges of the cycle, &pi;&sigma; is a long cycle.</p> <p>For each i&lt;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).</p> <p>Thus for each i&lt;j, &pi;(ij)&tau; is a big cycle, where &tau; does not involve i or j. In particular, &pi;(i)&ne;j. Since this is true for all i&ne;j, it follows that &pi; must be the identity. We get a contradiction since &sigma; is not a big cycle.</p>