5-regular graphs and the 3-dimensional rigidity matroid

Abstract

A bar-joint framework $(G,p)$ in Euclidean $d$-space is rigid if the only edge-length-preserving continuous motions arise from isometries of ${\mathbb{R}}^d$. In the generic case, rigidity is determined by the generic $d$-dimensional rigidity matroid of $G$. The combinatorial nature of this matroid is well understood when $d=1,2$ but open when $d\ge 3$. Jackson and Jordán 2005 characterised independence in this matroid for connected graphs with minimum degree at most $d+1$ and maximum degree at most $d+2$. Their characterisation is known to be false for $(d+2)$-regular graphs when $d\ge 4$ but when $d=3$ it remained open. Indeed they conjectured that their characterisation extends to 5-regular graphs when $d=3$. The purpose of this article is to prove their conjecture. That is, we prove that every 5-regular graph that has at most $3n-6$ edges in any subgraph on $n\ge 3$ vertices is independent in the generic 3-dimensional rigidity matroid.

26 pages, 3 figures