If a graph is -connected and has a graph minor satisfying , it is -linked. Write , so . The rooted branch-set reduction replaces the minor model by disjoint connected sets, the first containing any prescribed terminals separately, each missing at most of the remaining sets. Every prescribed pair then has at least common adjacent unused sets, allowing the connections to be selected successively. The reduction uses rooted separations of a graph, contraction of edges outside distinct branch sets, and a final Hall marriage theorem matching; the separation condition prevents a contraction from destroying access to the model.

Articles by others on the same topic (0)

There are currently no matching articles.