The extremal function for 3-linked graphs

A graph is k-linked if for every set of 2k distinct vertices {s1,…,sk,t1,…,tk} there exist disjoint paths P1,…,Pk such that the endpoints of Pi are si and ti. We prove every 6-connected graph on n vertices with 5n−14 edges is 3-linked. This is optimal, in that there exist 6-connected graphs on n vertices with 5n−15 edges that are not 3-linked for arbitrarily large values of n.