Given a graph $G$ with $n$ vertices, that has a perfect matching $M$, what is the maximal number of edges that $G$ can have without contradicting the uniqueness of $M$? 


Are examples of such extremal graphs known?



Densest Graphs with Unique Perfect Matching
Let $G$ be a graph with $2n$ vertices with a unique perfect matching $M$. Choose any $2$ edges from $M$ and consider the $4$ vertices present. In addition to the $2$ edges from the matching there can be at most $2$ more edges if we want the matching to be unique. Thus the number of edges must be less than or equal to $n + 2\binom{n}{2} = n^2$. 


This bound can certainly be realized. Let $G\_{2n}$ be the graph with vertex set
$$\{x\_i : 1 \leq i \leq n\} \cup \{y\_i : 1 \leq i \leq n\}$$ and edge set 
$$\{x\_ix\_j : 1 \leq i < j \leq n\} \cup \{x\_iy\_j : 1 \leq i \leq j \leq n\}.$$
We see that $G\_{2n}$ has $2n$ vertices and $n^2$ edges. Moreover $\{x\_iy\_i : 1 \leq i \leq n\}$ and the unique perfect matching in $G\_{2n}.$ Notice this is exactly the graph constructed by Wolfgang in his answer (and also alternatively constructed by Yoav Kallus in a comment to Wolfgang's answer). Furthermore Wolfgang asks if $G\_{2n}$ is the unique graph on $2n$ vertices with $n^2$ that has a unique perfect matching. We will now show this is the case.


Let $H$ be a graph on $2n$ vertices with $n^2$ edges such that $H$ has a unique perfect matching. Let $\{x\_iy\_i : 1 \leq i \leq n\}$ be the unique perfect matching in $H$. Let $H\_{ij}$ denote the subgraph induced by vertices $\{x\_i, y\_i, x\_j, y\_j\}$ for any $1 \leq i,j \leq n$. Then $H\_{ij}$ is a graph on $4$ vertices with $4$ edges for all $1 \leq i,j \leq n$. We know the number of edges in $H\_{ij}$ is bounded above by $4$ from our argument for the upper bound, and it must be exactly $4$ to have $n^2$ total edges. In fact each $H\_{ij}$ is isomorphic to the graph on vertex set $\{1,2,3,4\}$ with edge set $\{12,13,14,34\}$.


**Claim:** Fix $1 \leq i \leq n$. If $\deg\_{H\_{ij}}(x\_i) = 3$ for some $1 \leq j \leq n$, then $\deg\_{H\_{ik}}(y\_i) < 3$ for all $1 \leq k \leq n$.


*Proof)* If $\deg\_{H\_{ij}}(x\_i) = 3$, then $H\_{ij}$ has edge set $\{x\_iy\_i, x\_ix\_j, x\_iy\_j, x\_jy\_j\}$. Assume $\deg\_{H\_{ik}}(y\_i) = 3$ for some $k$, then $H\_{ik}$ has edge set $\{x\_iy\_i, x\_ky\_i, y\_iy\_k, x\_ky\_k\}$. But this contradicts $H$ having a unique perfect matching (check that $H\_{ijk}$, which is the subgraph of $H$ induced by vertices $\{x\_i,y\_i,x\_j,y\_j,x\_k,y\_k\}$, would have multiple perfect matchings by considering possible edges in $H\_{ik}$). **QED**


Now assume without loss of generality that the vertices are labelled such that $\deg\_{H\_{ij}}(y\_i) < 3$ always (or equivalently, the unique degree $3$ vertex in $H\_{ij}$ is always $x\_i$ or $x\_j$). Define a relation $x\_i \prec x\_j$ if and only if $x\_iy\_j$ is an edge in $H$.


**Claim:** $(\{x\_i : 1 \leq i \leq n\}, \prec)$ is a totally ordered set.


*Proof)* First note either $x\_i \prec x\_j$ or $x\_j \prec x\_i$ for any $i,j$ since either $x\_i$ or $x\_j$ in the degree $3$ vertex in $H\_{ij}$. We have $x\_i \prec x\_i$ since $x\_iy\_i$ is an edge of $H$. If $x\_i \prec x\_j$ and $x\_j \prec x\_i$, then $x\_i = x\_j$ otherwise the uniqueness of the prefect matching would be contradicted. Finally we verify transitivity. Take $x\_i, x\_j$ with $x\_i \prec x\_j$ and $x\_j \prec x\_k$. Assume $x\_k \prec x\_i$, then $H\_{ijk}$ has the prefect matching $\{x\_iy\_j, x\_jy\_k, x\_ky\_i\}$ with is a contraction. Thus $x\_i \prec x\_k$ and $\prec$ is transitive. **QED**


Now this total order on $\{x\_i : 1 \leq i \leq n\}$ describes an isomorphism $H$ to $G\_{2n}$ and therefore $G\_{2n}$ is the unique graph (up to isomorphism) with $2n$ vertices, $n^2$ edges, and a unique perfect matching.


