  Our input is a complete graph $G = (V,E)$ on $n$ vertices where each vertex
has a strict ranking of all other vertices in $G$. Our goal is to construct a
matching in $G$ that is popular. A matching $M$ is popular if $M$ does not lose
a head-to-head election against any matching $M'$, where each vertex casts a
vote for the matching in $\{M,M'\}$ where it gets assigned a better partner.
The popular matching problem is to decide whether a popular matching exists or
not. The popular matching problem in $G$ is easy to solve for odd $n$.
Surprisingly, the problem becomes NP-hard for even $n$, as we show here.
