\magnification=1200\noindent
{\bf Andrew Shapira }\smallskip\noindent
{\bf An Exact Performance Bound for an ${O (m+n)}$ 
Time
Greedy Matching Procedure} 
\vskip1cm

We prove an exact lower bound on $\gamma(G)$, the size of the smallest
matching that a certain $O(m+n)$ time greedy matching procedure may
find for a given graph $G$ with $n$ vertices and $m$ edges.
The bound is precisely Erd\"{o}s and Gallai's extremal function that
gives the size of the smallest maximum matching, over all graphs with $n$
vertices and $m$ edges.
Thus the greedy procedure is optimal in the sense that when only $n$
and $m$ are specified, no algorithm can be guaranteed to find a larger
matching than the greedy procedure.
The greedy procedure and augmenting path algorithms are seen to be
complementary: the greedy procedure finds a large matching for dense
graphs, while augmenting path algorithms are fast for sparse graphs.
Well known hybrid algorithms consisting of the greedy procedure followed
by an augmenting path algorithm are shown to be faster than the augmenting
path algorithm alone.
The lower bound on $\gamma(G)$ is a stronger version of Erd\"{o}s
and Gallai's result, and so the proof of the lower bound is
a new way of proving of Erd\"{o}s and Gallai's result.

\end