Is the $n$-cycles factorization in $S_n$ as product of $n-1$ transpositions unique?

Question

I'm studying Graph Theory, and I have a question. I'm trying to prove that the product of $n-1$ transpositions in $S_n$ is an $n$-cycle if and only if the associated graph of $n$ vertices ($i, j$ adjacent if and only if $(i j)$ is one of those transpositions) is a tree.

I think the proof assumes that the factorization of an $n$-cycle in $n-1$ transpositions always has the same structure, such as $(x_1 x_2)(x_1 x_3) \cdots (x_1 x_n)$, so the first entry of each permutation is always the same. I mean, those absolutely work for any $n$-cycle, and for any $x_1 \in \{1, \ldots, n\}$, but is it a given that those transpositions need to be like that?

Like, can't the first entry of each transposition be different than the others?

Answer 1

Certainly—for one thing, the transpositions $(a\ b)$ and $(b\ a)$ are the same, so the notion of "first entry" isn't even well defined.

Answer 2

As user994373 points out in the comments, $(1,3)(3,4)(1,2) = (1,2,3,4)$ gives an example of such a product in which there is no element common to every transposition.

---

An extended aside, which may be of interest to someone, if not necessarily you :P

I suspect that the proof given does not rely on this special structure, because it is a bit absurd even given the theorem statement. A product that has an element in common to every transposition does indeed yield not only a tree, but a star. The Halmosian reader* should be suspicious of this: if the truth were "a star", why would the theorem say "a tree" instead?

[Now, a priori it could be that the only trees that arise as these associated graphs are stars. This isn't the case, as the example shows, but if it were, the theorem would technically be true! Still, the suspicion would be warranted: by failing to point out the additional structure, the author would have been doing a huge disservice to the reader.]

On the other hand, stars do seem like the simplest case (at least to me) so it's not unreasonable that some sort of inductive argument has slid under the radar. Imagine "here's how it works for stars; and here's a procedure for getting any tree from a star; and here's how it works at each step of the procedure," where perhaps the middle step is not even written carefully/explicitly....

* "Don't just read it; fight it! Ask your own question, look for your own examples, discover your own proofs. Is the hypothesis necessary? Is the converse true? ... Where does the proof use the hypothesis?" [emphasis added]