Linkedness of Cartesian products of complete graphs

This paper is concerned with the linkedness of Cartesian products of complete graphs. A graph with at least $2k$ vertices is {\it $k$-linked} if, for every set of $2k$ distinct vertices organised in arbitrary $k$ pairs of vertices, there are $k$ vertex-disjoint paths joining the vertices in the pairs. We show that the Cartesian product $K^{d_1+1}\times K^{d_2+1}$ of complete graphs $K^{d_1+1}$ and $K^{d_2+1}$ is $\text{floor}(d_1+d_2)\mathrm{/}2$-linked for $d_1,d_2\ge 2$, and this is best possible. %A polytope is said to be {\it $k$-linked} if its graph is $k$-linked. This result is connected to graphs of simple polytopes. The Cartesian product $K^{d_1+1}\times K^{d_2+1}$ is the graph of the Cartesian product $T(d_1)\times T(d_2)$ of a $d_1$-dimensional simplex $T(d_1)$ and a $d_2$-dimensional simplex $T(d_2)$. And the polytope $T(d_{1})\times T(d_{2})$isasimplepolytope,a$(d_{1}+d_{2})$-dimensional polytope in which every vertex is incident to exactly $d_1+d_2$ edges. While not every $d$-polytope is $\text{floor}d\mathrm{/}2$-linked, it may be conjectured that every simple $d$-polytope is. Our result implies the veracity of the revised conjecture for Cartesian products of two simplices.