众所周知,两边点数相等的 kkk-正则二分图可以证明存在完美匹配。
那么对于二分图 G=(X,Y,E)G=(X,Y,E)G=(X,Y,E),满足 XXX 中点的度数相等,YYY 中点的度数相等,是否可以证明此时一定存在最大匹配数为 min(∣X∣,∣Y∣)\min(|X|,|Y|)min(∣X∣,∣Y∣),如何证明?