Search the corpus

    Disjoint paths joining two prescribed vertex sets in a k-connected graph

    P-UNL852970-06A2

    Area
    Topology
    Seen at
    UNL
    Years
    2006
    Status
    draft
    Contents

    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\).

    Solution submission

    Submit a solution on GitHub