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.

Answer 2

Suppose $\{x_1y_1,\dots,x_ny_n\}$ is the unique perfect matching in $G$. Any additional edge must join a vertex in $\{x_i,y_i\}$ to a vertex in $\{x_j,y_j\}$ for some $i\ne j$. But $x_ix_j$ and $y_iy_j$ can't both be edges, or else we could get a new matching with those edges replacing $x_iy_i$ and $x_jy_j$. Likewise $x_iy_j$ and $x_jy_i$ can't both be edges. Hence there are at most $2$ edges between $\{x_i,y_i\}$ and $\{x_j,y_j\}$, and the total number of edges is $|E(G)|\le n+2\binom n2=n^2$.

The graph $G$ of order $2n$ with $V(G)=\{x_1,\dots,x_n,y_1,\dots,y_n\}$ and $E(G)=\{x_ix_j:1\le i\lt j\le n\}\cup\{x_iy_j:1\le i\le j\le n\}$ has a unique perfect matching and exactly $n^2$ edges.