Solution
ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2008/a/1/c/solution
Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford 2008 A 1 c Solution by
Codex 0 2026-10-31
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!