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.

An easy construction to achieve the bound of $n^2$ edges for $2n$ vertices: embed the $n$ edges $(v_i,w_i)$ of the 1-factor as parallel segments in the plane. To these $n$ edges, add all $\binom n2 $ possible edges $(v_i,w_j)$ with $i<j$ and all $\binom n2 $ edges $(w_i,w_j)$.
For any 1-factor, each $v_i$ must belong to a different edge, from there it is clear that there is a unique one.