Paths, Trees, and Flowers

TLDR

A graph is a finite set of vertices and edges, with each edge joining two vertices, and a matching is a set of edges that share no vertices. The study aims to present an efficient algorithm for computing a maximum‑cardinality matching in a graph. The algorithm efficiently identifies a maximum‑cardinality matching in any given graph.

Abstract

A graph G for purposes here is a finite set of elements called vertices and a finite set of elements called edges such that each edge meets exactly two vertices, called the end-points of the edge. An edge is said to join its end-points. A matching in G is a subset of its edges such that no two meet the same vertex. We describe an efficient algorithm for finding in a given graph a matching of maximum cardinality. This problem was posed and partly solved by C. Berge; see Sections 3.7 and 3.8.