Graph with exactly one perfect matching

Question

How do I prove that if $G$ is a graph with $2n$ vertices and has exactly one perfect matching, then $|E(G)| \le n^2$?

Answer 1

Let $G$ be a graph with exactly one perfect matching $M$, $2n$ vertices and $m$ edges. Let $v$ and $w$ be two vertices that are endpoints of an edge of $M$ and let $d(v)=t$. A neighbor $u$ of $v$ different from $w$ is endpoint of an edge $e_u$ of $M$ and $w$ may not have an edge to the other endpoint of $e_u$ or we find an alternating 4-cycle, which would lead to a second perfect matching.

So the neighbors of $w$ must avoid $t-1$ vertices, which means that $d(v)+d(w)\leq t+((2n-1)-(t-1))=2n$. This is true for each of the $n$ matched pairs of vertices, so we find $2m=\Sigma_v d(v)\leq n\cdot 2n$, or $m\leq n^2$, as desired.

Note that, although we only cared about alternating 4-cycles, this bound is actually sharp: it is easy to construct (for any $n$) a graph with $2n$ vertices and $n^2$ edges that has exactly one perfect matching.