I think that the following proof of the fact that *every subgroup of index* $2$ *of a given group is normal* might count too. When I first came up with it (sometime during my sophomore year), I believed that I had just found the entrance to a *royal* road to mathematics. 

Let $H\leq G$ be such that $[G:H]=2$. We'll prove that every right coset of $H$ is equal to a left coset of $H$.

Since $[G:H]=2$, $G$ is both the union of two disjoint right cosets of $H$ and the union of two disjoint left cosets of $H$. Let us suppose that $G=He \cup Hx = eH \cup yH$ where $x,y\in G\setminus H$ and $e$ denotes the identity element of $G$. According to standard lore regarding the symmetric difference of sets,

$He \cup Hx = He \triangle Hx \triangle (He \cap Hx) = He \triangle Hx \triangle \emptyset = H \triangle (Hx\triangle \emptyset) = H\triangle Hx$

and

$eH \cup yH = eH \triangle yH \triangle (eH \cap yH) = eH \triangle yH  \triangle \emptyset = H \triangle (yH \triangle \emptyset) = H \triangle yH$.

Therefore, $H\triangle Hx = H\triangle yH$. Canceling $H$ on both sides of the latter equality—which is perfectly valid given that $(2^G, \triangle)$ is a group—we conclude that $Hx=yH$. Done.

If you consider that the prior argument doesn't qualify as awfully sophisticated, there is still another fancy way to derive the result in question. As a consequence of **P. Hall**'s famous marriage theorem, **M. Hall** proves in **Theorem 5.1.7** of his *Combinatorial Theory* that *if* $H$ *is a finite* index *subgroup of* $G$, *there exists a set of elements that are simultaneously representatives for the right cosets of* $H$ *and the left cosets of* $H$ (once he's proven the said theorem, he adds: "Simultaneous right-and-left coset representatives exist for a subgroup in a variety of other circumstances. This problem has been investigated by Ore [1][1]."). In the case $[G:H]=2$, this implies at once that every right coset of $H$ is equal to a left coset of $H$ and we are done...

Last but not least, $[G:H]=2 \Rightarrow H \trianglelefteq G$ in the case when $|G|<\infty$ can also be seen a consequence of the well-known fact according to which any subgroup of a finite group  whose index is equal to the smallest prime that divides the order of the group is of necessity a normal subgroup of the group. **B. R. Gelbaum** showcases in one of his books an *action-free* proof of this fact. He attributes both the fact and the *action-free* proof to **Ernst G. Straus**. Does any of you know on what grounds he did so? I have a Xerox copy of the relevant page in the book here. This is exactly what Gelbaum writes therein:

>At some time in the early 1940s Ernst G. Straus, sitting in a group theory class, saw the proof of the ... result [i.e., $[G:H]=2 \Rightarrow H \trianglelefteq G$] ... and immediately conjectured (and proved that night): ... IF G:H [sic] IS THE SMALLEST PRIME DIVISOR P of #(G) THEN H IS A NORMAL SUBGROUP.

P.S. The Galois-theoretic proof given by [Matthias Künzer][2] is just fabulous! 

  [1]: http://www.ams.org.pbidi.unam.mx:8080/journals/proc/1958-009-04/S0002-9939-1958-0100639-2/home.html
  [2]: http://mathoverflow.net/questions/42512/awfully-sophisticated-proof-for-simple-facts/78003#78003