Minimum degree conditions for graph rigidity

Abstract

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})$, every $n$-vertex graph with minimum degree at least $(n+d)/2-1$ is rigid in ${\mathbb{R}}^d$. For larger values of $d$, we achieve an approximate result: for $d=O(n/{\log }^{2}n)$, every $n$-vertex graph with minimum degree at least $(n+2d)/2-1$ is rigid in ${\mathbb{R}}^d$. This bound is tight up to a factor of two in the coefficient of $d$. As a byproduct of our proof, we also obtain the following result, which may be of independent interest: for $d=O(n/{\log }^{2}n)$, every $n$-vertex graph with minimum degree at least $d$ has pseudoachromatic number at least $d+1$; namely, the vertex set of such a graph can be partitioned into $d+1$ subsets such that there is at least one edge between each pair of subsets. This is tight.

18 pages