|
We prove that if the $2$-dimensional rigidity matroid of a graph $G$ on at least seven vertices
is connected, and $G$ is minimal with respect to this property, then $G$ has at most $3n-9$ edges.
This bound, which is best possible, extends Dirac's bound on the size of minimally $2$-connected graphs
to dimension two. The bound also sharpens
the general upper bound of Murty for
the size of minimally connected matroids in the case when the matroid is a rigidity matroid of a graph.
Our proofs rely on ear-decompositions of connected matroids
and on a new lower bound on the size of the largest circuit in a connected rigidity matroid,
which may be of independent interest.
We use these results to determine the tight upper bound on the number of edges in a minimally
redundantly rigid graph in two dimensions.
Furthermore, as an application of our proof methods,
we give a new proof for Murty's theorem.
Bibtex entry:
| AUTHOR | = | {Jord{\'a}n, Tibor}, |
| TITLE | = | {Ear-decompositions, minimally connected matroids, and rigid graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2022}, |
| NUMBER | = | {TR-2022-11} |