更新时间：2022-08-25 16:14
门杰定理(Menger's theorem)又称“Menger定理”，是关于图的连通性的一个定理，门杰定理断言：若X和Y是图G的两个不交的节点子集，k是一个正整数，则G上存在k条分别以X和Y中的节点为端点而且两两除端点外互不交的路，当且仅当每一个XY分离点集包含至少k个节点，上述的XY分离点集指G的这样一个节点子集，若从G上去掉该子集的所有节点，所得到的图不存在连X中节点与Y中节点的路，这个定理是门杰(K.Menger)于1927年首先发现的，于是，由此而得名。
1927年，Menger证明了图的连通性与图中连接两个顶点的不相交路的数目有关。Menger定理非常有用，由它产生了许多关于图的连通性的很多变种结论，而且它与Hall匹配定理与最大流量最小割定理以及其他一些离散数学中的重要结论都密切相关。
下面的定理就是Menger定理原先提出来的原始形式。
定理1(顶点形式的Menger定理) 设x和y为图G中两个不相邻的顶点，则G中内部不相交的(x，y)-路的最大数目=G中最小的xy-顶点分隔集的顶点数。
证明 将下文定理7用于G的对称有向图上即得。
推论2(Menger定理) 设p(G)≥k+1，则G为k-连通的当且仅当G中任意两个不相同顶点至少被k条内部不交的路所连接。
证明 必要性。反证，假设k-连通图G中存在两个顶点u，v，使得G中内部不相交的(u，v)-路的最大数日为m
充分性。反证，假设非平凡图G不是k-连通的，即κ(G)
引理3 设网络N的源为x，汇为y，且每弧的容量都为1，则
1)N中最大流的值等于N中弧不重的有向(x,y)-路的最大数目。
2)N中最小割的容量等于N中最小的xy-弧分隔集的弧数。
引理3提供了由最大流最小割定理推导Menger定理的桥梁。 ·
定理4(弧形式的Menger定理) 设x和y为有向图D中任意两顶点，则D中弧不重的有向(x,y)-路的最大数目=D中最小的xy-弧分隔集的弧数。
与后面无向图“顶点形式”的定理7和定理9相似，我们有以下无向图“边形式”的两个定理。令人惊奇的是，直到1955年，它们才首先被Ford和Fulkerson证明出来。
定理5(边形式的Menger定理) 设x和y为图G中任意两顶点，则G中边不重的(x，y)-路的最大数目=G中最小xy-边分隔集的边数。
证明 作图G的对称有向图，再用定理4即得。
G为k-边连通的↔从G中去掉任何k-1条边都不能使G不连通↔对G中任意两个顶点x和y，G中最小的xy-边分隔集的边数至少为k，由此，以下推论是显然的。
推论6(Menger定理) G为k-边连通的当且仅当G中任意两个顶点都至少被k条边不重的路所连接。
定理7(顶点形式的Menger定理) 设x和y为有向图D中两个不同顶点，且D中没有连x到y的弧，则D中内部不相交的有向(x，y)-路的最大数目=D中最小的xy-顶点分隔集的顶点数。
证明 由D作有向图D’如下：
于是易见，D'中一有向(x，y)-路与D中一有向(x，y)-路之间存在一一对应关系(通过将D'中一有向(x，y)-路上每一(v'，v'')弧缩成v；或将D中一有向(x，y)-路的每一中间顶点v分裂成弧(v'，v''))。又由于易见D'中二有向(x，y)-路为弧不重的↔D中对应的二有向(x，y)-路为内部不相交的。因此，D'中弧不重的有向(x，y)-路的最大数目=D中内部不相交的有向(x，y)-路的最大数目。
类似地，D'中最小的xy-弧分隔集的弧数=D中最小的xy-顶点分隔集的顶点数。再用定理4问题得证。证毕。