The extremal function for 3-linked graphs (Q947723)

A graph \(G\) is \(k\)-linked if for every set of \(2k\) distinct vertices \(\{s_1,s_2,\dots,s_k,t_1,t_2,\dots,t_k\}\) of \(G\) there exist \(k\) disjoint path \(P_1,P_2,\dots,P_k\) such that the endpoints of \(P_i\) are \(s_i\) and \(t_i\) for \(1\leq i\leq k\). A natural question is whether or not there is a function \(f(k)\) such that every \(f(k)\)-connected graph is \(k\)-linked. In this paper the authors prove that every 6-connected graph of order \(n\) with at least \(5n-14\) edges is 3-linked. This bound is best possible because there exist 6-connected graphs of order \(n\) with \(5n-15\) edges that are not 3-linked for arbitrarily large \(n\).