若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径（举例来说，有A、B集合，增广路由A中一个点通向B中一个点，再由B中这个点通向A中一个点……交替进行）。
主要性质
1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M，不匹配的边比匹配的边多一。
证明：
根据增广路的定义，P连通两个未匹配顶点，可知P的第一条和最后一条边都不属于M。
我们设，且.
由于P中的边交替出现，即.
我们可以令，即
由于,可知.
可知 n-1=2k, 所以n=2k+1，且匹配的边比不匹配的边多1.
2－不断寻找增广路可以得到一个更大的匹配M’，直到找不到更多的增广路。
证明：
我们可以构造一条另外的路径取代，从而找到一个更大的匹配。
，.
由性质1，在P中不匹配的边比匹配的边多1，那么在P'中，匹配的边比不匹配的边多1.
所以。
3－M为G的最大匹配当且仅当不存在M的增广路径。
引理1： 对于图G的任意两个匹配M和M'，它们的对称差的连通分支是
一条路径或者一个长度为偶数的圆。
证明：, e要么是M中的一条边，要么是M'中的一条边，但不能同时出现于M和M'中。且对于e的
邻边e'，e和e‘必然来自两个不同的匹配，因为一个顶点只能出现于一个匹配中。所以对于e的任意一个顶点u,
d(u)=1（没有通过顶点u与e相邻的边）或者d(u)=2 （e有一条公用顶点u的邻边）。
. 所以对称差中的连通分支要么是一条路径，要么是一个圆。
对于其中的圆，由于圆中的每一条边，其邻边必然来自不同的匹配中，所以圆的长度必然为偶数。
必要性：
假设M为G的最大匹配且存在M的增广路径P，由性质2，我们可以通过P来构建路径P'从而找到比M更大的匹配。
所以一定不存在M的增广路径。
充分性：
即如果不存在M的增广路径，那么M为G的最大匹配。
我们找到它的逆否命题：如果M不是G的最大匹配，那么一定存在M的增广路径。
要证明这个等价的逆否命题，我们必须利用引理1.
我们设M'是比M更大的一个G的匹配。我们找到它们的对称差，可知其连通分支为路径或圆。由于圆的
长度为偶数，所以必然有同样多的边来自M和M'。由于，存在至少一条路径，其中有k条边
来自于M，剩余的k+1条边来自M'。该条路径就是一条M的增广路径，所以我们必然可以找到一条M的增
广路径，该命题成立，所以充分性成立。
应用