A proof of Connellyʹs conjecture on 3-connected circuits of the rigidity matroid

A graph G=(V,E) is called a generic circuit if |E|=2|V|−2 and every X⊂V with 2⩽|X|⩽|V|−1 satisfies i(X)⩽2|X|−3. Here i(X) denotes the number of edges induced by X. The operation extension subdivides an edge uw of a graph by a new vertex v and adds a new edge vz for some vertex z≠u,w. Connelly conjectured that every 3-connected generic circuit can be obtained from K4 by a sequence of extensions. We prove this conjecture. As a corollary, we also obtain a special case of a conjecture of Hendrickson on generically globally rigid graphs.