A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid. (Q1405103)

A graph \(G= (V,E)\) is called a generic circuit if \(| E|= 2| V|- 2\) and every \(X\subset V\) with \(2\leq| X|\leq| V|- 1\) satisfies \(i(X)\leq 2| X|-3\) where \(i(X)\) is the number of edges induced by \(X\). The operator extension subdivides an edge \(uw\) of a graph by a new vertex \(v\) and adds a new edge \(uz\) for some vertex \(z\neq u,w\). The authors prove that every 3-connected generic circuit can be obtained from \(K_4\) by a sequence of extensions. This was conjectured by R. Connelly [see i.e. \textit{W. Whiteley}, Contemp. Math. 197, 171--311 (1996; Zbl 0860.05018)]. As a corollary the authors obtain a special case of a conjecture of \textit{B. Hendrickson} [SIAM J. Comput. 21, 65--84 (1992; Zbl 0756.05047)] on generically globally rigid graphs.