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 subset of V with 2 less than or equal to \X\ less than or equal to \V\ - 1 satisfies i(X) less than or equal to 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 znot equalu, w. Connelly conjectured that every 3-connected generic circuit can be obtained from K-4 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. (C) 2002 Elsevier Science (USA). All rights reserved.