Connectivity-Menger,s theorem
المؤلف:
Jean-Claude Fournier
المصدر:
Graph Theory and Applications
الجزء والصفحة:
63
28-7-2016
1822
Theorem 1.1 (Menger, vertex statement).
A simple graph G such that n ≥k+1 is k-connected if and only if any two distinct vertices of G are connected by k internally vertex-disjoint paths (that is pairwise with no other common vertices than their ends).
This is one of the major theorems in graph theory. Its proof is easy in one direction: the sufficient condition, since the existence of k vertex-disjoint paths between any two given vertices prevents the existence of fewer than k vertices by which removal would disconnect the graph. Indeed, the removal of less than k vertices in the graph cannot delete k paths linking two given vertices x and y, since these paths have no common vertices other than their ends x and y (the vertices removed are distinct from x and y). The necessary condition is less evident; a proof of this is given in Chapter 8 as an application of the theory of flows. In the meantime, as an exercise, it is interesting to try to prove it for the case k =2.
___________________________________________________________________________________
Graph Theory and Applications ,Jean-Claude Fournier, WILEY, page(63)
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
