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

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!

• No such graph if $n\le2$ so assume $n\ge3$. I guess the max is $n^2-2(n-1)$. Take a graph with three distinct vertices $a,b,c$ such that $N(a)=N(b)=\{c\}$. – bof Jun 19 '20 at 0:39

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| 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$$.