Minimum degree and pan-kk-linked graphs

For a kk-linked graph GG and a vector S→ of 2k2k distinct vertices of GG, an S→-linkage is a set of kk vertex-disjoint paths joining particular vertices of S→. Let TT denote the minimum order of an S→-linkage in GG. A graph GG is said to be pan-kk-linked if it is kk-linked and for all vectors S→ of 2k2k distinct vertices of GG, there exists an S→-linkage of order tt for all tt such that T≤t≤|V(G)|T≤t≤|V(G)|. We first show that if k≥1k≥1 and GG is a graph on nn vertices with n≥5k−1n≥5k−1 and δ(G)≥n+k2, then any nonspanning path system consisting of kk paths, one of which has order four or greater, is extendable by one vertex. We then use this to show that for k≥2k≥2 and n≥5k−1n≥5k−1, a graph on nn vertices satisfying δ(G)≥n+2k−12 is pan-kk-linked. In both cases, the minimum degree result is shown to be best possible.