关于Schrijver对Tutte-Berge公式证明中组件P为何是路径的疑问

嘿，我来帮你把这个困惑的点掰明白，其实得结合两个最大匹配的并图结构来推导~

首先补个关键的小背景：当你把两个最大匹配M和N的所有边放在一起构成一个图时，这个图里每个顶点的度数最多是2——毕竟每个匹配里一个顶点最多连一条边，两个匹配加起来最多两条。基于这个特点，这个图的每个连通组件只能是两种情况：要么是偶长度的环（边在M和N之间交替出现，不然顶点度数就会超过2），要么是交替路径（同样是M边和N边交替的路径）。

现在来看顶点t：我们已知N是一个不覆盖t的最大匹配，也就是说t在N里完全没有关联的边。那t在M∪N这个图里的度数最多是1——因为M是匹配，t最多在M里有一条边，N里是0条。

那t所在的连通组件P不可能是环，因为环里每个顶点的度数都是2，可t在N里没边，根本凑不出度数2的条件。所以P只能是路径。而且这条路径的端点一定包含t：路径内部的顶点度数都是2（需要同时在M和N里各有一条边），但t最多只有1条边（来自M），它没法满足内部顶点度数为2的要求，所以只能是这条路径的一个端点。

这样就对应上了证明里那句“As N misses t, P is a path with end t.”的推导逻辑啦。

备注：内容来源于stack exchange，提问作者licheng