# a lower bound for the maximum fraction of matchings not containing an edge

I am trying to prove the following statement (from book, page 317):

Let $$G(A,B,E)$$ be a bipartite graph, where $$A$$ and $$B$$ are the two disjoint sets of vertices s.t. $$|A|=|B|=n$$. Let the number of matchings of size $$k\le n$$, be $$m_k$$. If $$|E|>k$$ then there exists an edge $$e$$, such that $$\frac{m_{ne}}{m_k} \ge \frac{1}{n}$$, where $$m_{ne}$$ is the number of matchings of size $$k$$, that do not include/contain edge $$e$$.

The book gives a hint to use pigeonhole principle. But I am only able to get a weaker result.
Each matching of size $$k$$, contributes towards a matching of size $$k$$ not containing an edge, for $$|E|-k$$ edges. Thus as there are in total $$m_k$$ matchings, it can be seen as distributing $$(|E|-k)m_k$$ balls in $$|E|$$ bins. Thus by pigeonhole principle there is a bin (an edge) with at least $$\frac{(|E|-k)\cdot m_k}{|E|}$$ matchings which do not contain it. That is there is an edge $$e$$ such that $$m_{ne} \ge \frac{(|E|-k)\cdot m_k}{|E|}$$ $$\frac{m_{ne}}{m_k} \ge \frac{|E|-k}{|E|} \ge \frac{1}{|E|} \ge \frac{1}{n^2}$$

How can I prove that the lower bound is at least $$\frac{1}{n}$$ for some edge ?

Your approach has been working well all along, only to miss the promising transformation at the last step.

Instead of $$\frac{|E|-k}{|E|} \ge \frac{1}{|E|} \ge \frac{1}{n^2},$$ we can proceed as $$\frac{|E|-k}{|E|} =1 - \frac{k}{|E|} \ge1- \frac k{k+1}=\frac1{k+1}.$$

Since $$k\le n$$, i.e., $$\dfrac1{k+1}\ge\dfrac1{n+1}$$, we are not far from the goal $$\dfrac1n$$.

It takes a bit more effort to reach the goal. I will leave it to you to complete.

Here is a slightly easier proof. It shows, except possibly for graphs where all edges are separated, we can increase $$1/n$$ to $$1/2$$.

Consider whether there are incident edges in $$G$$.

• There are incident edges. Say, edge $$e_1$$ and $$e_2$$ are incident. Every matching (of size $$k$$) can contain at most one of them. So either at least 1/2 of the matching of size $$k$$ does not contain $$e_1$$ or at least 1/2 of the matching of size $$k$$ does not contain $$e_2$$. Note that $$1/2\ge 1/n.$$
• There are no incident edges. Then there are at most $$n$$ edges. Since each matching does not contain at least one of the $$|E|$$ edges, we have , if $$e$$ is the edge that is absent from the most matchings of size $$k$$,$$\frac{m_{ne}}{m_k}\ge \frac{1}{|E|} \ge \frac{1}{n}.$$

$$\checkmark$$