MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Given a connected undirected graph $G = (V,E)$, where each node has a minimum degree of $d$, find the minimum number $N$ such that there exists $N$ spanning trees $T_1, ..., T_N$, where for each node $v \in V$, either $v$ is an articulation point, i.e., the removal of $v$ disconnects the rest of the graph, or there exists some $1 \leq i \leq N$ such that $v$ is a leaf in tree $T_i$.

share|cite|improve this question
You want your graph not to have any cut vertices for this to be possible. Other than that, it's unclear what answer you are looking for. Do you want to bound $N$ in terms of some other data (minimum degree etc.)? Otherwise a simple answer is that for a 2-vertex connected graph $N\le |V|+1/2$, and equality is achieved for odd cycles. – Gjergji Zaimi Jun 8 '12 at 6:43
That should have been $N\le (|V|+1)/2$ – Gjergji Zaimi Jun 8 '12 at 6:43
Thanks for your answer. Yes, actually I want to bound the minimum degree of a node. Except for articulation points which are impossible to cover, all the rest should be covered by at least one tree. Please see the updated problem description. – Hongyang Jun 8 '12 at 7:39
If you have subsets $V_1, V_2, ..., V_k$ of $V$ such that $G-E(V_k)$ is connected for each $k$ and the $V_j$ cover $V$ then $N \leq k$. – hbm Jun 8 '12 at 21:59
I meant $G-E(V_j)$ is connected for each $j \leq k$. – hbm Jun 8 '12 at 23:20

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.