一般匹配多胞形的奇集约束

把 $S$ 内的度约束相加，得到

这只是连续容量计数。对真正匹配，内部边数还是整数；当 $|S|$ 为奇数时，多出的半个配对位置不能使用。奇集约束把这份奇偶信息放回 LP。

在二分图匹配多胞形公理库二分图匹配多胞形Bipartite matching polytope证明二分图的非负边变量与顶点度上界已给出匹配凸包，并用交替扰动区分分数可行点和分数顶点。中，偶环允许交替扰动，度约束已经足够；一般图的奇圈会锁住分数。补齐奇集以后，若仍试图构造分数极点，它就必须遇到一个紧的奇数区域。收缩这个区域，分别在内外处理，再按跨界边把两边匹配接起来，是整数性证明的重要机制。

五环排除的是半条额外匹配 ​

在五环上令每边 $1/2$。每个顶点的度和是一，但总边量为 $5/2$。取 $S=V$，奇集约束要求 $x(E)\le 2$，立即排除它。实际最多选两条互不接触的边，两条也确实可取，整数最优为二。

只加五环这一条割并不是一般图的完整算法。在较大图里，需要检查许多不同奇集，它们不一定是诱导奇环，甚至不一定对应当前增广路搜索中的一个 blossom。奇集指的是任意奇数顶点集合，内部可能还有弦和复杂子图。

在紧奇割两侧拼接匹配 ​

看三棱柱图：上三角形顶点为 $a,b,c$，下三角形为 $d,e,f$，跨边为 $ad,be,cf$。令九条边都取 $1/3$，每个顶点的度和都是一，上三角形 $S=\{a,b,c\}$ 的跨界总量也恰为一。

这份分数向量有明确分解：

每个分量都是完美匹配，每条边恰出现一次。收缩上三角形后，三种外侧匹配分别选择跨边 $ad,be,cf$；收缩下三角形也得到对应的内侧匹配。两边必须按照同一条跨边配对，才能还原原图匹配。例如使用 $ad$ 时，上面留下 $bc$、下面留下 $ef$，而不能随便把另一个跨边的内部方案接上。

为什么这个机制能证明完整定理 ​

先证明完美匹配版本：度约束为等式 $x(\delta (v))=1$，奇集条件等价于 $x(\delta (S))\ge 1$。对顶点数与边数组成的有序对作字典序归纳；空图由空匹配给出基例，不可行情形两边都为空。考察可行域的一个极点，删掉零边；若有值为一的边，移除其两端后归纳。剩下所有边都严格在零和一之间，每个顶点至少接触两条边。

如果全部图结点的度数都是二，支撑是若干环。奇数环分量被奇割条件排除；偶数环可以交替正反扰动，所以不可能形成分数极点。如果某个图结点度数大于二，则 $|E|>|V|$；仅靠 $|V|$ 条度等式不够钉住一个极点，必须有一条新的紧奇割 $x(\delta (S))=1$。可取 $S$ 和补集都至少含三个顶点，因为单点及其补集的割只是已有度等式。

分别收缩 $S$ 与其补集，删去被收缩区域的内部边，保留每条跨割边的原身份及可能产生的平行记录。新超级点的度和等于一；收缩奇数个顶点为一个顶点保持奇偶性，所有奇割条件都能从原图继承。两张更小的图由归纳假设可分解为完美匹配。它们在跨割每条边上的总权重相同，可以把权重细分后按跨边配对，再展开，得到原 $x$ 的匹配凸组合。一个分数极点不可能有这样的非平凡分解，矛盾。

最后把普通匹配化为完美匹配：复制一份图 $G^{\prime }$，原边及复制边都赋值 $x_e$，每对对应顶点 $v,v^{\prime }$ 间加入权重 $1-x(\delta (v))$ 的竖边。所有度和变成一。任意奇集写成 $A\cup B^{\prime }$，令 $C=A\setminus B,D=B\setminus A$；$C,D$ 至少一个大小为奇数。不妨 $C$ 为奇数，复制图的该割容量至少为

其余割项非负；两份图的对称边确保这一下界。于是复制图满足完美匹配条件，分解后再投影回原图，就得到普通匹配的凸组合。

一般匹配的加权对偶除了顶点价格 $y_v\ge 0$，还给每个奇集价格 $z_S\ge 0$。边 $uv$ 的价格覆盖条件为

目标是最小化 $\sum _v{y}_v+\sum _S((|S|-1)/2)z_S$。弱对偶公理库线性规划对偶Linear programming duality · LP duality从线性约束生成对偶界，并以弱对偶、强对偶和互补松弛连接两侧最优解。让任何这样的价格成为匹配权重上界。五环单位权例中，令 $z_V=1$、其他价格零，上界就是二，与两条边的匹配相遇。

Edmonds 增广路算法公理库Edmonds blossom 算法Edmonds' blossom algorithm · Blossom algorithm通过识别并收缩奇交替环，在一般图中保持增广路存在性并求最大匹配的算法。收缩的是相对于当前匹配和交替森林的 blossom；这里证明凸包时收缩的是分数向量的一条紧奇割。两种收缩都利用奇偶结构，但对象与不变量不同，不能把任意奇集当作增广路算法中可随时收缩的 blossom。

约束数可以指数多，却不妨碍这个描述有算法价值：真正求解时通常通过分离算法寻找当前违反的奇集，再加入需要的约束，而不是预先列出全部子集。完整匹配定理说明这些约束足够，具体分离成本则需要另一份算法分析。