4
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ You should add the easy case of a non-connected graph. $\endgroup$ Jul 20, 2010 at 7:39
  • 3
    $\begingroup$ 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. $\endgroup$ Jul 20, 2010 at 15:54
  • $\begingroup$ 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$. $\endgroup$
    – user7760
    Jul 20, 2010 at 21:30
  • $\begingroup$ I modified the proof, hopefully now it does work. $\endgroup$ Jul 20, 2010 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.