2
$\begingroup$

Quoting from the book (page 272) Graphs and Geometry by Lovasz, we have the following theorems regarding the characterization of rigid graphs in the pane.

Theorem 1: A graph $G$ is rigid in the plane if and only if for every decomposition $G=G_1\cup\cdots \cup G_k$ into the union of graphs with at least one edge, we have $$\sum_i (2|V(G_i)|-3)\geq 2n-3,$$ where $V(G_i)$ denotes the set of vertices of $G_i$ and $n$ is the number of vertices of $G$.

Theorem 2: Let $G$ be a multigraph on $n$ nodes. $G$ contains $k$ edge-disjoint spanning trees of $G$ if and only if for every partition $\mathcal{P}$ of $V(G)$, the number of edges connecting different classes is at least $k(|\mathcal{P}|-1)$.

It is stated (without proof) in the book that we have the following corollary of the above theorems.

Corollary: A graph is rigid in the plane if and only if every graph obtained by doubling an edge of $G$ contains two edge disjoint spanning trees.

I would like to know how the Corollary follows from Theorem 1 and Theorem 2. May be this is easy but I am unable to see how. Any help will be appreciated.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .