Menger's theorem


Also found in: Wikipedia.

Menger's theorem

[′meŋ·ərz ‚thir·əm]
(mathematics)
A theorem in graph theory which states that if G is a connected graph and A and B are disjoint sets of points of G, then the minimum number of points whose deletion separates A and B is equal to the maximum number of disjoint paths between A and B
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.
References in periodicals archive ?
Theorem 2.1 (Menger's Theorem [1]) Let G be a k-connected graph, and let x and y be a pair of distinct vertices in G.
Since k(G) > [k.sub.3](G) = k, by Menger's Theorem, there exist at least k + 1 internally disjoint x-y paths [P.sup.1], [P.sup.2], ..., [P.sup.k+1] in G([v.sub.1]).
If y' = z', since k(G) > [k.sub.3](G) = k, by Menger's Theorem, it is easy to construct k + 1 internally disjoint S-trees.
Note that Menger's Theorem justifies the definition (see e.g.
Hence, the graph G is [(3/ln 2)ln n + O(ln ln-connected by Menger's Theorem [1].