最小点覆盖是指在图中选择最少的点，使得所有的边至少有一个端点被选中。
结论：二分图的最小点覆盖就是最大匹配数。
首先可以证明：最小点覆盖大于等于最大匹配。
- 因为最大匹配给出了完全没有公共端点的若干条边，要确保这些边都至少有一个端点被选中，那么至少需要选取与边数相同数量的点。
其次可以构造一个等于最大匹配数的覆盖方案，即可确认前述证明的下界可行。
假定对图 G 已经求到一个最大匹配。
现在从左侧的未匹配点出发寻找增广路，很显然不能找到。当寻找结束后，左侧未访问的点和右侧访问了的点的集合就是最小点覆盖。
首先这个操作出来的点就是点覆盖，因为对于
- 对于匹配边，是从右到左访问，
- 如果这条边被访问过，那么右侧点被访问过，那么右侧选中；
- 如果这条边没被访问过，则左侧未访问，那么左侧选中。
- 对于非匹配边，是从左到右访问，
- 如果这条边被访问过，那么左侧先访问，并进入右侧，右侧被访问过，那么右侧选中；
- 如果这条边没被访问过，说明左侧点未访问，则左侧选中。
综上，对于匹配边和非匹配边，都有一边是选中的，即实现点覆盖。
现在要证明选中的点数跟匹配数是一样的，很显然，对于匹配边，我们已经正好选了这么多点了。也就是我们需要证明非匹配边中选取的点并不额外增加点数，即一定都是对应另外一条匹配边的。
- 对于非匹配边，是从左到右访问，
- 如果这条边被访问过，那么左侧先访问，并进入右侧，右侧被访问过，那么右侧选中。此情况下，右侧必然有另外一条匹配边，否则这形成了一条增广路（从左侧未匹配点开始，到右侧一个未匹配点结束）。
- 如果这条边没被访问过，说明左侧点未访问，则左侧选中。我们的增广是从左侧未匹配点出发的，如果左侧点未访问，则左侧点一定是匹配过的。
综上，选取的点数就是最大匹配数。所以最小点覆盖等于最大匹配。