拟阵交定理

共同独立集必须同时支付两套独立性预算。任意切分 $U\bigsqcup (E\setminus U)$ 后，落在 $U$ 的元素至多占用 $M_1$ 的 $r_1(U)$ 个独立位置，另一侧至多占用 $M_2$ 的 $r_2(E\setminus U)$ 个位置，所以每个切分都给上界。定理的力量在于：总有一个切分把这个显然上界压到恰好可达。

交换图是增广路思想的拟阵版本。单次加入可能在两个拟阵中分别制造回路；沿路径交替删换元素，可以把一边修好的独立性传递到另一边，直到找到同时可加入的终点。无路时，可达与不可达区域反过来形成秩证书。

在二分图 $G=(L\bigsqcup R,E)$ 的边集上，令 $M_1$ 是按左端点分组、每组至多取一条边的分割拟阵，$M_2$ 对右端点作同样限制。共同独立集恰是匹配，所以二分图最大匹配是拟阵交的特例。对边 $ax,bx$（$L=\{a,b\},R=\{x\}$），最大共同独立集大小为 $1$；取 $U=\varnothing$，有 $r_1(U)+r_2(E)=0+1$，min–max 两侧相等。

共同独立集族通常不是拟阵。四顶点路径的三条边记为 $e_1,e_2,e_3$；匹配 $\{e_2\}$ 与 $\{e_1,e_3\}$ 都共同独立，但无法从后者选一条加入前者而保持匹配，违反拟阵交换公理。因此不能把 ${\mathcal{I}}_1\cap {\mathcal{I}}_2$ 当成第三个拟阵并直接使用普通贪心。

公式中的第二项必须是 $r_2(E\setminus U)$。若误写成 $r_2(U)$，切分就不再覆盖共同独立集的两部分，连显然上界都无法推出。有限性也用于增广算法终止和基数 min–max；无限拟阵交需要额外公理与不同定理。

交换图算法每次把共同独立集增大一，最终同时产出一个最大解和集合 $U$ 的最优性证书。二分图匹配中的交替路与顶点覆盖对偶由此成为同一增广–证书结构的具体表现；增广路理路增广路Augmenting path相对于当前匹配，边在未匹配与已匹配之间交替且两个端点均未匹配的路径。不再局限于图上的顶点序列，而由两套拟阵交换关系生成。

拟阵交还描述同时满足图森林约束、分组容量约束或线性无关约束的选择问题。加权拟阵交允许元素带权并优化共同独立集的总权值，但需要势函数、最短路或线性规划等更强算法；它不是把本页无权增广证明中的“大小”机械替换成“权重”。