1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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\}$. $\endgroup$ – bof Jun 19 '20 at 0:39
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.