Prove that if \(G\) is a \(k\)-connected graph and \(S,T\subset V(G)\) are disjoint subsets of vertices, each of size \(k\), then there are \(k\) pairwise disjoint paths \(P_1,\ldots,P_k\) and labelings \[ S=\{s_1,\ldots,s_k\},\qquad T=\{t_1,\ldots,t_k\} \] such that \(P_i\) is a path from \(s_i\) to \(t_i\) for each \(i\).
Disjoint paths joining two prescribed vertex sets in a k-connected graph
P-UNL852970-06A2
- Area
- Topology
- Seen at
- UNL
- Years
- 2006
- Status
- draft