为了便于叙述，我们将二分图分为左边的点与右边的点来叙述。我们称二分图匹配成功的边为匹配边，称匹配成功的点为匹配点，二分图匹配数为匹配边的条数。 于是最小顶点数等于二分图匹配数。
先证明最小顶点数大于等于二分图匹配数。从反面考虑，少于二分图匹配数的顶点绝对不可能覆盖二分图，因为这些顶点无法覆盖所有的匹配点。
再证明至少存在一个数量为二分图匹配数的顶点集，可以覆盖二分图。
正面来做，我们先来找这个集合。
我们来对二分图进行染色，从右边任取一个非匹配点开始，我们沿着二分图的边走，遵循这样一种走法：“标记右边未匹配边的顶点，并从右边未匹配边的顶点出发，按照边：未匹配->匹配->未匹配…，的原则标记途中经过的顶点，则最后一条经过的边必定为匹配边。重复上述过程，直到右边不再含有未匹配边的点。”（注意标记就是染色的意思）（注意孤立点没路走，直接染色，不要忽视）（为了让读者深入理解，笔者故意不画图，让读者自己画）
那么左边的染色点加上右边的非染色点便是我们要找的顶点集。
下面证明该集合的点数为匹配数且覆盖二分图。
-—————————–
先证明该集合点数为匹配数：
我们观察所有的匹配边，如果他被走过，说明他是被从左往右走的，那么它的两个端点都被染色；如果他没有被走过，说明已经没有多余的边可以到他的左端点了，那么他的两个端点都没有被染色。也就是说对于所有的匹配边，要么两个端点都被染色，要么两个端点都未被染色。
现在我们可以断言，如果左边的染色点集是左边的匹配点集的子集且右边的非染色点集是右边的匹配点集的子集，那么染色点个数等于匹配数。这里不好描述，但好证明，笔者不证明了。
下面来证明上诉前提条件是恒成立的。
右边的非染色点集是右边的匹配点集的子集，可以用反证：如果存在一个右边非染色点不属于右边的匹配点集，那么这个点肯定是非匹配点，这与我们的染色规则矛盾。
左边的染色点集是左边的匹配点集的子集，我们依旧反证：如果存在一个左边的点不属于左边的匹配点集，那么说明有一个右边的非匹配点可以走到当前的非匹配点，这与二分图最大匹配矛盾。
-—————————–
再证明该点集覆盖二分图：
我们考虑边，分三种
- 右端点为非染色点，这些边被右边的非染色点集覆盖
- 右端点为染色点，左端点为染色点，这些边被左边的染色点集覆盖
- 右端点为染色点，左端点为非染色点，都在说这样的边不存在，然而证明过程却给得极其含糊不清。
二分图的构造就讲的含糊不清，为了让读者感到区别，我故意在上面的叙述中引用了带有歧义的染色规则。
因为上述叙述至少有一个反例：
img
这个叙述应该改为从右边的非匹配点出发，走二分图，每次从右往左走都走非匹配边，每次从左往右走都走匹配边，（注意这里并没有说走过的点不能再走一次，也没有说起点只有一个)直到无路可走或走入循环，染色所有经过的点和边，重复此操作，直到不能再次染色为止。
依据现在的走法，上图反例不复存在，可以得出正确覆盖。对走法进行影响未改变上文所有证明，下面来证明新走法不存在右端点为染色点，左端点为非染色点的边，这就很明显了，这种边在我们新的走法里面是不存在的，因为可以走这样的边，并染色。
-—————————–
综合得到二分图最小顶点覆盖数等于二分图匹配数。