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|&gt;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$