最小点覆盖
同样的转化为图G=(V,E)，则问题转化为：
在图G中选取尽可能少的点，使得图中每一条边至少有一个端点被选中。
这个问题在二分图问题中被称为最小点覆盖问题。即用最少的点去覆盖所有的边。
结论：由König定理可知最小点覆盖的点数 = 二分图最大匹配
最大独立集
依旧转化为图G=(V,E)，则问题转化为：
在图G中选取尽可能多的点，使得任意两个点之间没有连边。
这个问题在二分图问题中被称为最大独立集问题。
结论：最大独立集的点数 = 总点数 – 二分图最大匹配
证明：
假设最大独立集的点数为|U|，二分图最大匹配的匹配数为|M|，最大匹配中所有顶点集合为EM
先证明 |U|≤|V|-|M|
M中任意一条边的两个端点是连接的，所有对于M中的边必有一个端点不在|U|集合中，所以|M|≤|V|-|U|
再证明|U|≥|V|-|M|
首先我们知道一定有|U|≥|V|-|EM|，即将最大匹配的点删除之后，剩下的点一定都不相连。
接下来我们考虑能否将M集合中的一个端点放入U中：
假设(x,y)属于M，存在(a,x),(b,y)，且a,b都在U中，则会出现两种情况： 如果(a,b)连接，则有一个更大的匹配存在，矛盾 如果(a,b)不连接，a->x->y->b有一个新的增广路，因此有一个更大的匹配，矛盾
故有a,b两点中至多只有1个点属于U，则我们总是可以选取x,y中一个点放入集合U
所以|U|≥|V|-|EM|+|M|=|V|-|M|
综上有|U|=|V|-|M|