Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Have found some sufficient conditions for this to be true, but no necessary conditions so far. Sufficient, at least, is for each $H_i$ to be a union of blocks of $G$, in such a way that $H_1,H_2,\ldots H_r$ constitute a "partition" of the blocks of $G$. In particular, it holds whenever $H_1,H_2,\ldots H_r$ are the blocks of $G$. Can provide a proof of this if anyone is interested. Have not managed to show that this is a necessary condition (nor to find a counterexample showing that it isn't). – Bart Patzer Apr 28 '12 at 20:00
In general, if the proposition holds for some $\{H_i\}$, then it holds for any "coarser partition" of $\{H_i\}$ as well. – Bart Patzer Apr 28 '12 at 20:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.