Every $d(d+1)$-connected graph is globally rigid in ${\mathbb{R}}^d$

Abstract

Using a probabilistic method, we prove that $d(d+1)$-connected graphs are rigid in ${\mathbb{R}}^d$, a conjecture of Lovász and Yemini. Then, using recent results on weakly globally linked pairs, we modify our argument to prove that $d(d+1)$-connected graphs are globally rigid, too, a conjecture of Connelly, Jordán and Whiteley. The constant $d(d+1)$ is best possible.

arXiv comment10 pages, 1 figure