= Short augmenting paths in a dense bipartite graph
{title2=$\delta(G)>n/2\Longrightarrow\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\leq2n^4m_{k+1}$.
Back to article page
