Minimum degree conditions for graph rigidity

Michael Krivelevich, Alan Lew, Peleg Michaeli

We study minimum degree conditions that guarantee that an $n$-vertex graph is rigid in ${\mathbb{R}}^d$. For small values of $d$, we obtain a tight bound: for $d=O(\sqrt{n})$, ever…