1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 unknown
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.
Technical Report of the Egerváry Research Group on Combinatorial Optimization, 2001, Issue TR-2001-08