Loading...
Please wait, while we are loading the content...
Similar Documents
A Proof of Menger's Theorem
| Content Provider | Semantic Scholar |
|---|---|
| Author | Pyre, Jackman |
| Copyright Year | 1969 |
| Abstract | Here is a more detailed version of the proof of Menger’s theorem on page 50 of Diestel’s book. First let’s clarify some details about “separating.” Given two sets of vertices A and B in G, a third set of vertices W separates A from B if every path from a vertex in A to a vertex in B contains a vertex from W. We say that a path is an A-B path if it’s first vertex is in A, it’s last vertex is B, and none of its internal vertices is in A or B. If every A-B path contains a vertex of W then W is separating. (The argument here is similar to that used to show that any two vertices connected by a walk are connected by a path.) So as a special case, W = A separates A from B since a path that starts in A includes at least that vertex from A. Thus the definition is not exactly the same as saying that after removing W there remains a vertex in A and a vertex in B that can no longer be connected. Let us define k(G, A, B) to be the smallest number of vertices in a set that separates A from B. Since either A or B separates A from B, |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://math.unm.edu/~loring/links/graph_s05/Menger.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
