二分图匹配的匈牙利算法有两个重要的定理
定理一：当没有增广路的时候，必然是二分图的最大比配
定理二：当从某一个点出发找不到增广路，那么经过几次增广之后从该点出发一样找不到增广路
定理一的证明：
直接证明比较难证，我们可以证明该命题的逆否命题：
当二分图未达到最大匹配，则一定有增广路
此时有已匹配的边的集合M，有另一集合N的匹配边数比M多一条，可知此时M未到最大匹配，令集合H = {M∪N - M∩N}，可以得到H中相关的点的度数不是一就是二，并且形成了多个联通块儿，其中的边形成了M和N的边交替连接的情况，且不是偶数环就是一条链。因为N始终比M多一条边，所以一定有一条链是10101...101形式的，这样就一定形成了一条增广路。得证。此时其他的联通块N和M的边完全可以互相转换。
定理二的证明：
方法一：直接证明
若用0代表未匹配的边，1代表已匹配的边，可以知道当从某点A出发找不到增广路的时候，则从A出发的路径必然是0101......101形式的，即以未匹配边开头，已匹配边结束的链的集合。令X是从A出发某一路径的点集，因为增广链需要两头是未匹配的点，如果后来某次增广涉及到X中的点，那么X中至少有一个点连向一个未匹配的点，如果是这样的情况，那么在上次增广A的时候就可以找到一条增广路了，两者相悖，所以如果第一次从A未找到增广路，那么之后的所有增广操作都没法改变和A相连的联通块，A一直没有增广路。
方法二：逆推证明：证明某次增广操作不会让原本无增广路的A点有增广路
若用0代表未匹配的边，1代表已匹配的边，某时刻，A有一条增广路，将增广操作倒回，即在A的增广路中找一条1010......0101样式的链，姑且称为逆增广路，将该链反转，易得该次操作大致可以将A得增广路分为三块，而和A相连的那一块尾端一定是连向一条未匹配的点，A一直有增广路，则不存在某次增广操作会让原本无增广路的A点有增广路
