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é.