Perfect matchings in bipartite graphs.

Question

Question: $G$ is a bipartite graph where $|X| = |Y| = n$ and $|E| \geq n^2 - \frac{2n}{3} + 3$.

$X$ and $Y$ are the set of vertices and $E$ is the set of edges.

Prove that $G$ has a perfect matching.

My approach:

I tried solving the question but when you plug in values like $n=3$, $|E| \geq 9-2+3 \implies |E|\geq10$. How can this be? When $n = 3$, every vertex can be connected to only $3$ other vertices. Therefore maximum number of edges should be $9$ but this is clearly not the case here.

Answer 1

We have to check that $G$ satisfies the conditions of Hall’s Marriage Theorem. Suppose to the contrary, that there exists a subset $W$ of $X$ of size $1\le k\le n$ such that $|N_G(W)|\le k-1$. Then

$$n^2 - \frac{2n}{3} + 3\le |E|\le |W|||N_G(W)|+|X\setminus W||Y|\le$$ $$ k(k-1)+(n-k)n.$$

$$k^2-(n+1)k+\frac{2n}{3}-3\ge 0$$

Since $1\le k\le n$, we have $k^2-(n+1)k\le –n$, so $-n+\frac{2n}{3}-3\ge 0$ and $-n-9\ge 0$, a contradiction.

Answer 2

We will prove that if $|E|\geq n^2-n+1$ then $G$ has a perfect matching (note that this result is sharp because biparite graph $K_{n,n-1}$ has exactly $n^2-n$ edges and, obviously, doesn't have perfect matching).

Let $X=\{x_1, x_2, \ldots, x_n\}$ and $Y=\{y_1, y_2, \ldots, y_n\}$.

We will use probabilistic argument. Consider any bijection $\sigma\colon X\rightarrow Y$ (if we suppose that $X=Y=\{1,2,\ldots, n\}$ then $\sigma$ is just one of the $n!$ permutations of the set $\{1,2,\ldots, n\}$). Let $\xi(\sigma)$ be number of $i$ such that $(x_i, \sigma(i))$ is an edge of graph $G$. Note that if $\xi(\sigma)=n$ for some $\sigma$ then $G$ has a perfect matching (which corresponds to bijection $\sigma$). Therefore

Now, consider expected value of $\xi$ (we assume that every bijection $\sigma$ has the same probability $\frac{1}{n!}$). Note that $\xi(\sigma)=\xi_1(\sigma)+\xi_2(\sigma)+\ldots+\xi_n(\sigma)$, where $\xi_k(\sigma)$ equals $1$ if $(x_k,\sigma(x_k))$ is an edge of $G$ and $0$ otherwise. From linearity of expected value we obtain $$ \mathbb{E}[\xi]=\mathbb{E}[\xi_1]+\mathbb{E}[\xi_2]+\ldots+\mathbb{E}[\xi_n]. $$ Let $v_i$ be a degree of $x_i$ in the graph $G$. Note that $\mathbb{E}[\xi_k]$ equals $\frac{v_k}{n}$ (because in $Y$ there exactly $v_k$ vertices whic connected with $x_k$). Hence, $$ \mathbb{E}[\xi]=\frac{v_1+v_2+\ldots+v_n}{n}=\frac{|E|}{n}\geq\frac{n^2-n+1}{n}=n-1+\frac{1}{n}. $$ Therefore, for some bijection $\sigma_0$ inequlaity $\xi(\sigma_0)\geq n-1+\frac{1}{n}$ holds. But $\xi(\sigma_0)$ is integer not greater than $n$, so $\xi(\sigma_0)=n$. Thus, as mentioned before, $G$ has a perfect matching which corresponds to $\sigma_0$.

For original problem we just need to prove that $n^2-\frac{2n}{3}+3\geq n^2-n+1$ (which equivalent to $\frac{n}{3}+2\geq 0$), so problem is solved.