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$.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
