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.

  • $\begingroup$ 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 $\endgroup$ Jan 29 '19 at 1:47
  • $\begingroup$ I am sorry, I don't see how what you said relates to what I asked. $\endgroup$
    – joh dorian
    Jan 29 '19 at 1:55
  • $\begingroup$ 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. $\endgroup$ Jan 29 '19 at 1:57
  • 1
    $\begingroup$ 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. $\endgroup$ 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.

  • $\begingroup$ what is $|N_G(W)|$ $\endgroup$
    – joh dorian
    Jan 29 '19 at 3:48
  • $\begingroup$ @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. $\endgroup$ 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.


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.