Vertex-disjoint paths in sparse graphs I'm looking for a graph $G$ on $n$ vertices with the following properties


G doesn't have too many edges, $O(nlog(n))$ or $O(n)$ would be perfect
For random k disjoint pairs of vertices $(s_i,t_i)$ there is a path that links $s_i$ to $t_i$ for each $i$ such that all of these paths are vertex-disjoint. This statement should be true with high probability p.


The goal is to find $G$ such that $k$ is maximal. I'm not very precise on $k$ and the number of edges as well as on p (but let's say large constant p is fine or even better something that goes to 0 with n) because I don't know what is possible.

EDIT: I rephrased the question in terms of average case instead of worst case since worst case won't give many vertex-independent paths as pointed out by Chandra Chekuri.

Thanks,
André.
A hypercube has $O(n\log n)$ edges and satisfies your property for $k\leq\frac{\log_2 n+1}{2}$:


S. Madhavapeddy, and I. H. Sudborough, "A topological property of hypercubes: node disjoint paths", Proc. IEEE SPDP, 532-539, 1990.