# Build minimum number of spanning trees to cover all nodes in a graph as leaves

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$.

-
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