TR-2001-08

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 K₄ 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.

Keywords:
Graphs, Connectivity, Rigidity

Bibtex entry:

@techreport{egres-01-08,

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

}