TOPICS
Search

Menger's n-Arc Theorem


Let G be a graph with A and B two disjoint n-tuples of graph vertices. Then either G contains n pairwise disjoint AB-paths, each connecting a point of A and a point of B, or there exists a set of fewer than n graph vertices that separate A and B.

Harary (1994, p. 47) states the theorem as "the minimum number of points separating two nonadjacent points s and t is the maximum number of disjoint s-t paths." Skiena (1990, p. 178) states the theorem as "a graph is k-connected graph iff every pair of vertices is joined by at least k vertex-disjoint paths" (Menger 1927, Whitney 1932).


See also

k-Connected Graph

Explore with Wolfram|Alpha

References

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Menger, K. "Zur allgemeinen Kurventheorie." Fund. Math. 10, 95-115, 1927.Menger, K. Kurventheorie. Leipzig, Germany: Teubner, 1932.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

Referenced on Wolfram|Alpha

Menger's n-Arc Theorem

Cite this as:

Weisstein, Eric W. "Menger's n-Arc Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Mengersn-ArcTheorem.html

Subject classifications