Short augmenting paths in a dense bipartite graph ($\delta (G)>n/2⟹\text{an augmenting path of length at most three}$)

The two sides have $n$ vertices each. Given a nonperfect matching in a graph, choose unmatched vertices $u,v$ on opposite sides. An unmatched neighbour of either supplies a one-edge augmenting path in a matching. Otherwise their neighbours are matched; the matched left vertices corresponding to $N(u)$ and the set $N(v)$ have total size greater than $n$, so they intersect. This supplies the alternating path in a graph $u,b,a,v$ with $ab$ in the matching in a graph. Repeated augmentation produces a perfect matching.

Choose such an augmentation deterministically. Its reverse is specified by at most four vertices, giving at most $2n^4$ preimages for a matching in a graph of the next size. Thus the matching generating function coefficients satisfy $m_k\le 2n^4{m}_{k+1}$.