Mendelsohn-Dulmage theorem
Theorem [1]. Let [math]G=(S,T;E)[/math] be a bipartite graph, and let [math]X \subseteq S[/math], [math]Y \subseteq T[/math]. If [math]G[/math] has a matching covering [math]X[/math] and also a matching covering [math]Y[/math], then it has a matching covering [math]X \cup Y[/math].
The following is a generalization to matroids by Kundu and Lawler.
Theorem [2]. Let [math]M_1=(E,r)[/math] and [math]M_2=(E,r)[/math] be two matroids on the same ground set [math]E[/math], and let [math]X[/math] and [math]Y[/math] be both common independent sets of [math]M_1[/math] and [math]M_2[/math]. Then there exists a common independent set [math]Z[/math] such that [math]\mathrm{span}_{M_1}(Z) \supseteq \mathrm{span}_{M_1}(X)[/math] and [math]\mathrm{span}_{M_2}(Z) \supseteq \mathrm{span}_{M_2}(Y)[/math].
References
- ↑ N.S. Mendelsohn, A.L. Dulmage Some generalizations of the problem of distinct representatives, Canadian Journal of Mathematics, 10 (1958) 230- 241, DOI link
- ↑ S. Kundu, E.L. Lawler, A matroid generalization of a theorem of Mendelsohn and Dulmage, Discrete Mathematics, Vol. 4 (1973), 159-163, DOI link
