Maximum number of edges of a bipartite connected graph with vertex classes of size $n$ and with no perfect matching

Question

At most how many edges can a connected bipartite graph with $n$ vertices in each class can have so that there is no perfect matching?

If we omit the connectedness condition, then the maximum is $n(n-1)$ ($K_{n,n-1}$ with an isolated vertex is an example; the upper bound is proven by induction - if we assume there are at least $n^2 - n + 1$ edges, then there is a vertex of degree $n$; removing it and a neighbour of degree at most $n-1$ does the job).

However, in the connected case I have no idea even for an answer. Any help appreciated!

Answer 1

A bipartite graph $G$ with $n$ vertices in bipartite sets $X$ and $Y$ has no perfect matching iff the condition of Hall’s marriage theorem. That is, if there exists a subset $W$ of $X$ such that $k’=|N_G(W)|<|W|=k$. If $G$ is connected then $k>1$. Keeping the set $N_G(W)$ we can add edges to $G$ assuring that each vertex of $W$ is adjacent to each vertex of $N_G(W)$ and each vertex of $X\setminus W$ is adjacent to each vertex of $Y$. Clearly, the augmented graph is connected iff $|W|<n$ and we can add no more edges keeping the set $N_G(W)$. Thus a maximal connected graph satisfying the question requirements has $$kk’+(n-k)n\le k(k-1)+(n-k)n=n^2-k(n-k+1)$$ edges and the maximum $n^2-2(n-1)$ is attained iff $k=2$ or $k=n-1$.