{"id":"arxiv/2609.05058","url":"https://arxiv.org/abs/2609.05058","tags":["math.CO"],"score":0,"title":"Rigidity of complements of bounded-degree graphs","domain":"math.CO","source":"arxiv","authors":["John Haslegrave","Peleg Michaeli","Anthony Nixon"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-04","reactions":{}}