On sufficient degree conditions for a graph to be k-linked

A graph is k-linked if for every list of 2k vertices {s₁,..., s_k,t₁,..,t_k}, there exist internally disjoint paths P₁,...,P_k such that each P_i, is an s _i,t_i-path. We consider degree conditions and connectivity conditions sufficient to force a graph to be k-linked. Let D(n,k) be the minimum positive integer d such that every n-vertex graph with minimum degree at least d is k-linked and let R(n,k) be the minimum positive integer r such that every n-vertex graph in which the sum of degrees of each pair of non-adjacent vertices is at least r is k-linked. The main result of the paper is finding the exact values of D(n,k) and R(n,k) for every n and k. Thomas and Wollan [14] used the bound D(n,k) ≤ (n + 3k)/2 - 2 to give sufficient conditions for a graph to be k-linked in terms of connectivity. Our bound allows us to modify the Thomas-Wollan proof slightly to show that every 2k-connected graph with average degree at least 12k is k-linked.