A proof of Connelly's conjecture on 3-connected generic cycles

Alex Berg, Tibor Jordán

Published in:
J. Comb Theory B 88 (2003) 77-97.


A graph G=(V,E) is called a generic cycle if |E|=2|V|-2 and every X \subset V with 2 \leq |X| \leq |V|-1 satisfies i(X) \leq 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 \not= u,w. R. Connelly conjectured that every 3-connected generic cycle 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.

Graphs, Connectivity, Rigidity

Bibtex entry:

AUTHOR = {Berg, Alex and Jord{\'a}n, Tibor},
TITLE = {A proof of Connelly's conjecture on 3-connected generic cycles},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2001},
NUMBER = {TR-2001-08}

Last modification: 29.12.2020. Please email your comments to Tamás Király!