A graph G=(V,E) is called *k-rigid* in **R**^{d} if |V| ≥ k+1 and
after deleting at most k-1 arbitrary vertices the resulting graph is generically
rigid in **R**^{d}. A k-rigid graph G is called *minimally k-rigid*
if the omission of an arbitrary edge results in a graph that is not k-rigid.
It was shown in [7] that the smallest possible number of edges is
2|V|-1 in a 2-rigid graph in **R**^{2}. We generalize this result, provide an
upper bound for the number of edges of minimally 2-rigid graphs (for any d) and
give examples for minimally k-rigid graphs in higher dimensions.

Bibtex entry:

@techreport{egres-12-21,

AUTHOR | = | {Kaszanitzky, Vikt{\'o}ria and Kir{\'a}ly, Csaba}, |

TITLE | = | {On minimally k-rigid graphs}, |

NOTE | = | {{\tt www.cs.elte.hu/egres}}, |

INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |

YEAR | = | {2012}, |

NUMBER | = | {TR-2012-21} |