# Perfect matchings in bipartite graphs.

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.

• If there are no graphs with $n=3$ that satisfy the given condition, then any property at all is true of all the graphs with $n=3$ satisfying that condition: see en.wikipedia.org/wiki/Vacuous_truth Jan 29 '19 at 1:47
• I am sorry, I don't see how what you said relates to what I asked. Jan 29 '19 at 1:55
• You seem to have argued that when $n=3$ no graphs can exist that satisfy the property. True enough, but it's still true that "all the graphs" satisfying that property with $n=3$ have perfect matchings, simply because there are no such graphs -- so this isn't an obstacle to the claim being true. Jan 29 '19 at 1:57
• The theorem says: if you find an $(n,n)$-bipartite graph with $n^2-\frac23n+3$ edges, that graph will have a perfect matching. You will never find a $(3,3)$-bipartite graph with $3^2-\frac233+3$ edges. Therefore, the theorem says nothing in the case $n=3$. There is no contradiction here. The theorem only says something interesting about $(n,n)$ bipartite graphs with $n\ge 5$ vertices. Jan 29 '19 at 3:02

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.

• what is $|N_G(W)|$ Jan 29 '19 at 3:48
• @johdorian The neighborhood of $W$ in $G$, that is the set of all vertices in $Y$ adjacent to some element of $W$, see the linked page. Jan 29 '19 at 3:50

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.