Paths, Trees, and Flowers I: Matching-Duality Theorem — the Maximum Cardinality of a Matching Equals the Minimum Capacity-Sum of an Odd-Set CoverResearch Paper
A matching in a graph is a set of edges no two of which share a vertex. Finding a matching of maximum cardinality is one of the basic problems of combinatorial optimization: it models pairing tasks (workers to shifts, kidney donors to recipients, players to rounds), it is a subroutine of algorithms for the travelling salesman and Chinese postman problems,…