ABSTRACT

A matching in a graph G is a set of independent edges; that is to say, a set of edges no two of which share a vertex. It is no surprise that the study of such a simple concept should have begun early in the history of graph theory. Nor is it surprising that the idea of a matching should arise in many different contexts as well. One can take the position that there are two main historical sources for the study of matchings. One can associate these sources with two individuals: the Dane Julius Petersen in the area of regular graphs and the Hungarian De´nes Ko¨nig in the area of bipartite graphs.