Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2008/a/1/c/solution

In the vertex form of Menger's theorem, for distinct nonadjacent vertices of a finite graph, the maximum number of pairwise internally vertex-disjoint – paths equals the minimum size of an – vertex separator. A separator is a subset of vertices other than whose deletion leaves no – path; internally disjoint paths may share their endpoints but no other vertices. Equivalently, between disjoint vertex sets the maximum number of mutually vertex-disjoint connecting paths equals the minimum size of a separating vertex set, where endpoints may be deleted in that set version.

New to topics? Read the docs here!