Prove that $\exists a,g,h\in G\colon h=aga^{-1}, g\neq h ,gh=hg$ in a finite non-abelian group $G$. Let $G$ be a finite and non-abelian group.  How do I prove the following statement? $$\exists a,g,h\in G \colon\quad h=aga^{-1},\ g\neq h ,\ gh=hg.$$
Thanks in advance.
 A: Using the induction by $|G|$, we can suppose that all subgroups of $G$ are Abelian, i.e. $G$ is a Miller–Moreno group.  The structure of these groups are well-known (see What can we say of a group all of whose proper subgroups are abelian?). They are of 2 kinds:
1) $|G|=p^m$. Let $H<G, |H|=p^{m-1}$. Since $H$ is invariant and is not in the centre, it contains conjugate elements.
2) $|G|=p^mq^n$. Then, e.g., $P$ with $|P|=p^m$ is invariant of the type $(1,1,\ldots, 1)$ and $Q$ with $|Q|=q^n$ is cyclic, so $P$ is not in the centre and the proof is similar to above one.
A: Here is an outline which avoids the Miller-Moreno classification.  It requires a couple (challenging!) exercises.
By induction on group order, we can assume every proper subgroup of $G$ is abelian.  This is enough to conclude $G$ is solvable.
Because $G$ is solvable, there is a maximal subgroup which is also normal - call it $M$.
So $M$ is a maximal subgroup, which is also normal.  Thus $G/M$ is cyclic of prime order.  Choose a $g\in G$ such that $\bar{g}$ generates $G/M$.
Then we cannot have $g$ centralizing $M$, for otherwise $G$ would be abelian. So there is an $x\in M$ such that $x^g\neq x$.  However, both $x^g$ and $x$ are in $M$, so $[x^g,x]=1$.
A: Here is a slight variation of the other two answers.
The idea is still to use the observation that we can assume all proper subgroups are abelian.
Note now that it is sufficient to find a proper normal subgroup, which is not central (since it is proper, it will be abelian, so we just need two distinct conjugate element in it, which we get since it is normal and not central).
To show that any minimal non-abelian group (minimal non-abelian means precisely that all proper subgroups are abelian and the group itself is not abelian) has such a subgroup, let us note the following: 
Any proper subgroup of any quotient of a minimal non-abelian group is abelian (easy exercise).
A minimal non-abelian group is not simple (I could not find a really elementary proof of this, but it follows easily from observing that any non-normal Sylow subgroup will be central in its normalizer and applying Burnside's transfer theorem).
Finally, since the center is never maximal, we can find our proper normal non-central subgroup by pulling back a proper non-trivial normal subgroup from the quotient by the center.
