Rigidity of complements of bounded-degree graphs

Source abstract

Maxwell observed that the graph of any rigid generic framework in $\mathbb{R}^d$ on $n$ vertices has at least $dn-\binom{d+1}{2}$ edges. In this article we prove that graphs whose complement has maximum degree at most two and no component isomorphic to a triangle or a square are rigid in the maximum dimension allowed by this observation. In particular, this determines the precise maximum dimension in which the graph obtained from a complete graph $K_{2m}$ by deleting a perfect matching is rigid, resolving a recent conjecture of Lew. We also deduce bounds on the rigidity of complements of bounded-degree graphs more generally, which significantly improve existing degree-based bounds.