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 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 Kd1+1 × Kd2+1 of complete graphs Kd1+1 and Kd2+1 is ⌊(d1 + d2)/2⌋-linked for d1, d2 ≥ 2, and this is best possible. This result is connected to graphs of simple polytopes. The Cartesian product Kd1+1 × Kd2+1 is the graph of the Cartesian product T(d1) × T(d2) of a d1-dimensional simplex T(d1) and a d2-dimensional simplex T(d2). And the polytope T(d1) × T(d2) is a simple polytope, a (d1 + d2)-dimensional polytope in which every vertex is incident to exactly d1 + d2 edges. While not every d-polytope is ⌊d/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.