Do noncyclic groups of order $p^n$, $n>1$ always have a subgroup isomorphic to $C_p\times C_p$? If $p=2$, then the quaternion group is a counterexammple, so let $p$ be an odd prime. Are there any groups like the quaternion groups for odd primes (i.e., they have a center of order $p$ and every nontrivial subgroup contains the center) that would also serve as counterexamples?
 A: No. The only $p$-groups with no subgroups isomorphic to $C_p \times C_p$ are the cyclic groups of order $p^n$ and the quaternion groups of order $2^{n+3}$ for $n \geq 0$.
This is Theorem 5.4.10.ii on page 199 of Gorenstein's Finite Groups, Theorem 12.5.2 on page 189 of M. Hall's Theory of Groups, Theorem 5.3.7 on page 114 of Kurzweil–Stellmacher's Theory of Finite Groups, Theorem 6.11 on page 189 of Isaacs's Finite Group Theory, Satz III.8.2 on page 310 Of Huppert's Endliche Gruppen, Proposition 5.3.6 on page 136 of Robinson's textbook for a Course in the Theory of Groups, Theorem IV and V in §62-63 on pages 73-75 in Burnside's Theory of Groups (1ed), and Theorem V and VI in §104-105 on pages 131-132 of Burnside's Theory of Groups (2ed). Aschbacher's Finite Group Theory is another standard reference, but it only contains the reduction as proposition 23.9 on page 109 (the actual result though is exercise 4 on page 115).
None of the proofs are particularly short, but all are pretty easy to read.

In particular, every non-cyclic, non-quaternion finite $p$-group contains a subgroup $C_p \times C_p$. If we assume $Z(G)$ has order $p$, then $C_p \times C_p$ cannot equal $Z(G)$, so either it intersects it trivially or $Z(G)$ is a proper subgroup of $C_p \times C_p$ and any complement to $Z(G)$ intersects it trivially. Thus we have proved:
Proposition If $G$ is a finite $p$-group with $|Z(G)|=p$ which contains no non-identity subgroup intersecting the center trivially, then $G$ is cyclic or quaternion.
