A short proof that matching matroids are transversal

✍ Scribed by Eberhard Triesch

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 165 KB
• Volume: 5
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/0893-9659(92)90103-g

✦ Synopsis

We present an elementary proof of the well-known theorem of E&nor& and Fkdkerson that a matroid is a matching matroid if and only if it is transversal. Suppose G = (V, E) is a simple graph. It is well-known that match(G), the collection of all X C V which are covered by some matching in G, is the system of independent sets of a matroid which (following Welsh [l]) we again denote by match(G). For A c V, let match(G, A) denote the restriction of match(G) to A. A matroid M is called a matching matroid if there exist G and A as above such that M = match(G,A). A matroid M is called transversal if there exist a bipartite graph H and a subset A of one color class of H such that M = match(H,A). Edmonds and Fulkerson, who studied matching problems because of their rich applications in Combinatorial Optimization (see, e.g., [2]), introduced matching matroids in 1965 (cf. [3]) and proved the following striking fact: THEOREM 1. A matroid is a matching matroid if and only if it is transversal.