In a prior [post](https://mathoverflow.net/questions/226583/densest-graphs-with-unique-perfect-matching) regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices.


Analogously, what is the densest bipartite graph with unique Hamiltonian cycle?



What is the densest bipartite graph with unique Hamiltonian cycle?
The OP asks for the densest bipartite graph having a exactly one Hamiltonian cycle. We remark that in [Graphs with exactly one Hamiltonian cycle](http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190010110/abstract), John Sheehan shows that a graph on $n$ vertices with exactly one Hamiltonian cycle can have at most $\lfloor n^2/4\rfloor + 1$ edges and exhibits a graph $H\_n$ achieving this bound. Furthermore the author states $H\_n$ in the only graph achieving this bound. We will answer the OP's question by "bipartizing" the argument and construction of Sheehan.


Observe that a bipartite graph with a Hamiltonian cycle must have an even number of vertices. Let $G$ be a graph with vertices $\{x\_i: 1 \leq 2n\}$ labeled so that $C = x\_1x\_2\cdots x\_{2n}$ is the unique Hamiltonian cycle of $G$. Every edge of $G$ can be regarded as a chord of $C$. We let $C(G;l)$ denote the set of chords in $G$ of length $l$. So, elements of $C(G; l)$ will look like $x\_ix\_{i+l}$ with incides taken modulo $2n$. If $l > 1$ and $x\_i x\_{i+l}$ is a chord of $G$, then $x\_{i+1} x\_{i+l+1}$ cannot be a chord of $G$ otherwise $G$ would have more than one Hamiltonian cycle. This implies $|C(G;l)| \leq n$ for $l > 1$. In fact we can say $|C(G;2l-1)| < n$ for $l > 1$ because if $|C(G;2l-1)| = n$, then $G$ would contain a Hamiltonian cubic subgraph and hence at least three Hamiltonian cycles. Also, we see $|C(G,n)| < n/2$. So far, this is Sheehans's argument. Using the assumption that $G$ is bipartite we see that $|C(G; 2l)| = 0$ for $l > 0$.


Let $m$ denote the number of edges of $G$. We compute and see
$$m = \sum\_{l=1}^n |C(G;l)| \leq n(n+1)/2 + 1.$$


Consider the bipartite graph $G\_{2n}$ with vertices $\{x\_i : 1 \leq i \leq 2n\}$ and edges
$$\{x\_i x\_{i+1} : 1 \leq i \leq 2n\} \cup \{x\_{2i-1}x\_{2j} : 2i < 2j < 2n,
\; 1 \leq i < n-2\}.$$
Then $G\_{2n}$ has $2n$ vertices, $n(n+1)/2 + 1$ edges, and a unique Hamiltonian cycle $C = x\_1x\_2 \cdots x\_{2n}$. We remark graph $G\_{2n}$ can be obtained from Sheehan's $H\_{2n}$ by deleting the "non-bipartite" edges.


