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 ≥ |X| |V| 1 satisfies i(X) ≤ 2|X| 3. Here denotes the number of edges induced by X. The operation extension subdivides an edge uw new vertex v adds vz for some z ≠ u, w. Connelly conjectured that 3-connected can be obtained from K4 sequence extensions. We prove this conjecture. As corollary, we also obtain special case conjecture Hendrickson on generically globally rigid graphs.