The proof that a permutation and its conjugate have the same cycle structure from Cooper's notes I've been idly reading "Cooper's Notes" on graph theory the past few days.
Following one example, he states (see $\S2.10$ Conjugates) that

"the permutation and its conjugate have the same cycle structure."

where a conjugate of a permutation $a$ is defined as $b^{-1}ab$ for an arbitrary permutation $b$ on the same set.
How interesting! I think. It's followed by a theorem:

Theorem 2: The conjugate of $a=(x_1\:x_2\:\dots\:x_n)\dots$ by $b$ is $c=a^b=(b(x_1)\:b(x_2)\dots\:b(x_n))\dots$

no problem yet. Then the proof begins:

Proof: We'll show that $ab=bc$ from which it follows that $b^{-1}ab=c$.

Wait a minute. First of all, $c$ is defined as $b^{-1}ab$. Shouldn't it be the other way around? Show that $b^{-1}ab=c$ means $ab=bc$?
Second, and more importantly, all that this shows is that $ab$ has the same cycle structure as $bc$. Why should $ab=bc$ mean that $c$ has the same cycle structure as $a$?
The proof itself is short, which I reproduce here:

Now $ab(x_1)=b(a(x_1))=b(x_2)$ and $bc(x_1)=c(b(x_1))=b(x_2)$ Thus
$ab$ and $bc$ have the same effect on the symbol $x_1$. Similarly they
have the same effect on any symbol in the cycle notation for $a$. If
$z$ is any other symbol then it's fixed by $a$ so
$ab(z)=b(a(z))=b(z)$. Since $z$ is not present in the cycle notation
for $c$ it's fixed by $c$ and so $bc(z)=c(b(z))=b(z)$. We've thus
shown that $ab$ and $bc$ behave identically on all symbols so $ab=bc$.

What am I missing? Why does this proof have anything at all to do with the Theorem? Note that while I'd be interested in seeing a different proof, I'm more interested in why this specific proof works.
 A: Let's call the theorem:

"the permutation and its conjugate have the same cycle structure."

Now take a permutation $\sigma$ written as a product of disjoint cycles
$$\sigma = c_1 \dots c_l$$
The conjugate is
$$a \sigma a^{-1} = (a c_1 a^{-1}) \dots (a c_l a^{-1}) \tag{1}$$ which according to theorem 2 is a product of same length cycles. That are disjoint because the conjugation is bijective. This proves the theorem.
Remember that conjugation is a group homomorphism: this is what equation $(1)$ states.
A: This is admittedly not an answer to your question, but just another proof of the claim.

The cycle structure of a permutation $\sigma \in S_n$ shows itself when we consider the action of $\langle \sigma \rangle$ as a group of permutations on the set $X:=\{1,\dots,n\}$. By the Orbit-Stabilizer Theroem, we get:
$$|O_\sigma(i)||\operatorname{Stab}_\sigma(i)|=o(\sigma), \space\forall i\in X \tag 1$$
where:
$$\operatorname{Stab}_\sigma(i):=\{\sigma^k\mid \sigma^k(i)=i\} \le \langle\sigma\rangle, \space\forall i\in X \tag 2$$
Now, given $\tau\in S_n$, it is $(\tau\sigma\tau^{-1})^k=\tau\sigma^k\tau^{-1}$ (induction on $k$), so we get:
\begin{alignat}{1}
\operatorname{Stab}_{\tau\sigma\tau^{-1}}(i)&=\{\tau\sigma^k\tau^{-1}\mid (\tau\sigma^k\tau^{-1})(i)=i\} \\
&=\{\tau\sigma^k\tau^{-1}\mid \tau(\sigma^k(\tau^{-1}(i)))=i\} \\
&=\{\tau\sigma^k\tau^{-1}\mid \sigma^k(\tau^{-1}(i))=\tau^{-1}(i)\} \\
&=\{\tau\sigma^k\tau^{-1}\mid \sigma^k \in \operatorname{Stab}_\sigma(\tau^{-1}(i))\} \\
&=\tau\operatorname{Stab}_\sigma(\tau^{-1}(i)) \tau^{-1}, \space\forall \tau\in S_n,\forall i\in X\\
\tag 3
\end{alignat}
whence:
$$|\operatorname{Stab}_{\tau\sigma\tau^{-1}}(i)|=|\operatorname{Stab}_\sigma(\tau^{-1}(i))|, \space\forall \tau\in S_n,\forall i\in X \tag 4$$
But since $\forall \tau\in S_n, o(\tau\sigma\tau^{-1})=o(\sigma)$, we get that $(4)$ implies (again by the Orbit-Stabilizer Theorem):

$$|O_\sigma(\tau^{-1}(i))|=|O_{\tau\sigma\tau^{-1}}(i)|, \space\forall \tau\in S_n, \forall i\in X
\tag 5$$

Therefore, for every $\tau\in S_n$, the orbits induced by $\langle \tau\sigma\tau^{-1}\rangle$ and $\langle \sigma\rangle$ are pairwise of equal size. Moreover, if we denote by $\mathcal{O}$ the set of orbits, we have:

\begin{alignat}{1}
|\mathcal{O}_{\tau\sigma\tau^{-1}}| &= \frac{1}{o(\tau\sigma\tau^{-1})}\sum_{i=1}^{n}|\operatorname{Stab}_{\tau\sigma\tau^{-1}}(i)| \\
&=\frac{1}{o(\sigma)}\sum_{i=1}^{n}|\operatorname{Stab}_\sigma(\tau^{-1}(i))| \\
&=\frac{1}{o(\sigma)}\sum_{i=1}^{n}|\operatorname{Stab}_\sigma(i)| \\
&=|\mathcal{O}_\sigma| \\
\tag 6
\end{alignat}

So, given $\sigma\in S_n$, for every $\tau\in S_n$ the natural actions of $\langle\sigma\rangle$ and $\langle\tau\sigma\tau^{-1}\rangle$ on $X$ induce the same number of orbits of the same size in pairs, namely $\sigma$ and $\tau\sigma\tau^{-1}$ have the same cycle structure.
