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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You should add the easy case of a non-connected graph. $\endgroup$
    – Benoît Kloeckner
    Commented 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$
    – Yuval Filmus
    Commented 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
    Commented Jul 20, 2010 at 21:30
  • $\begingroup$ I modified the proof, hopefully now it does work. $\endgroup$
    – Yuval Filmus
    Commented Jul 20, 2010 at 22:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .