3
$\begingroup$

Let $G$ be a finite connected simple graph. By the union $H\cup K$ of two graph $H$ and $K$ we shall mean the graph with edge-set $E(H)\cup E(K)$ and vertex-set $V(H)\cup V(K)$.

For which collections of edge-disjoint subgraphs $H_1,H_2,\ldots,H_r$ with $H_1\cup H_2\cup\cdots\cup H_r=G$ is it true that every spanning tree $T$ of $G$ is a union $T=T_1\cup T_2\cup\cdots\cup T_r$ with $T_i$ a spanning tree for $H_i$?

I suspect this holds at least when $H_1,H_2,\ldots,H_r$ are the blocks (that is, the maximal biconnected subgraphs) of $G$...

Does it alter the conclusion if we omit the assumption that $G$ is simple?

Very thankful for any help.

  • 1
    In general, if the proposition holds for some $\{H_i\}$, then it holds for any "coarser partition" of $\{H_i\}$ as well.2012-04-28

0 Answers 0