Greedy Matchings in Bipartite Graphs with Ordered Vertex Sets

Hans U. Simon

We define and study greedy matchings in vertex-ordered bipartite graphs. It is shown that each vertex-ordered bipartite graph has a unique greedy matching. The proof uses (a weak f…