如何证明：若二分图中的匹配M非最大匹配，则存在M-增广路径？

首先得给你点个赞，你想到引入更大的最大匹配这个思路，完全是正确的核心方向！咱们一步步把这个证明拆明白，把你困惑的地方打通：

先明确几个关键定义 #

• M-匹配边：属于匹配M的边；M-非匹配边：不属于M的边
• M-增广路径：一条交替经过M-非匹配边和M-匹配边的路径，且路径的首尾两个顶点都是未被M匹配的顶点（也就是这两个顶点不在M的任何一条边上）

核心证明步骤 #

假设M不是最大匹配，那必然存在一个最大匹配M'，满足 |M'| > |M|（|X| 表示集合X的元素个数）。接下来咱们看两个匹配的对称差：

G' = M Δ M' = (M - M') ∪ (M' - M)

简单说，G'就是所有只在M里或者只在M'里的边组成的子图。

1. 分析G'的结构特性 #

因为匹配的定义是任意两条边不共享顶点，所以每个顶点在M里最多连1条边，在M'里也最多连1条边。那么每个顶点在G'中的度数只能是0、1或2：

• 度数0：顶点在M和M'里都没有匹配边，或者在两个匹配里的是同一条边
• 度数1：顶点只在M或只在M'里有一条匹配边
• 度数2：顶点在M和M'里各有一条匹配边（且这两条边不同）

所以G'的连通分量只能是两种情况：

• 偶环：环上的边交替来自M和M'，因为每个顶点度数是2，必须一进一出分别属于不同匹配。这种环里M和M'的边数完全相等，对两个匹配的边数差没有影响。
• 路径：路径的两个端点度数是1，中间顶点度数是2。

2. 从边数差推导增广路径的存在 #

因为 |M'| > |M|，所以G'里来自M'的边数一定比来自M的边数多。而偶环里两边边数相等，那多出来的边必然来自路径分量：

• 每条路径分量里，M'的边数要么等于M的边数，要么比M多1（因为路径是交替边，首尾度数为1的话，最后一条边必然是M'的边）
• 要让总边数M'更多，至少存在一条这样的路径：M'的边数比M多1

3. 验证这条路径就是M-增广路径 #

咱们看这条特殊路径的首尾顶点：

• 路径起点v：它在G'里的边是M'的边（因为路径里M'边多），那v在M里一定是未匹配的——如果v在M里有匹配边，那这条边要么在M'里（但M'是匹配，v只能有一条边，矛盾），要么不在G'里（那这条边也属于M'，还是矛盾）
• 同理，路径终点u也是M-未匹配顶点
• 这条路径是交替走M'边（对M来说是非匹配边）和M边（匹配边），完全符合M-增广路径的定义！

这样就证明了：只要M不是最大匹配，就一定存在这样的M-增广路径。

内容的提问来源于stack exchange，提问作者sktsasus