定理描述
數學上有許多定理，它們陳述某個集合中元素的最小個數等於另一個集合中元素的最大個數。下面將要介紹的就是這樣一個“最小～最大”定理，稱之為Menger定理。Menger定理有許多不同的表現形式，像Hall定理、女生結婚問題、集合代表元問題等。這裡介紹的是其在圖論網路中的形式。
Menger定理：設u和v是圖G的不鄰接的兩個頂點，則u—v分離集中頂點的最小個數等於G中內部不相交u—v路的最大個數。
定理證明
證：[歸納法]若圖G存在m個內部不相交u—v路，則u—v分離集中頂點數最少應為m。所以我們只需證明當最小分離集個數為m時，必存在m條內部不相交的u—v路即可。
不妨設m個分離點為v1,v2,...vm，所以我們只需考慮從u，v分別存在到v1,v2,...vm的不交路即可。考察包含u的連通分支E（包含v1,v2,...vm），對E內部頂點數作歸納。當內部無點時u直接與v1,v2,...vm相連此時顯然成立，假設當頂點數小於等於n時成立。當為n+1時去掉內部一點a及其所有邊，若此時不存在小於m的內部分離集，則由歸納法知成立。否則，若去掉a後vi孤立（最多只有一個點孤立），則將a取代vi後條件仍成立。由歸納假設存在到v1,v2,..vi-1,a,...vm的不交路，而vi只與a相連故成立。若去掉後存在m-1個分離點（不會小於m-1），則存在u到這些分離點及a的不交路，同理易知存在u到v1,v2,...vm的不交路（由分離點將其分為兩部分使頂點數減小，運用歸納假設知）。綜上n+1時不論何種情況都存在u到v1,v2,...vm的不交路，同理v也存在v1,v2,...vm的不交路，所以定理得證。
