Take the 2-minute tour ×  I have a graph $G(V,E)$ and a tree
$T(V',E')$ where $|V|=|V'|$ and $T$ is isomorphic to a subgraph
of $G$. In other words I found a spanning tree of $G$ and made
one of its nodes act as the root.  I now have 2 problems I want
to look at:    1. If I remove a node from $G$ what is the
optimal way to determine if a new $T$ exits and if so find it.
2.Assume $v_0$ is the root of $T$. I'm given an arbitrary node
$v_i$ and need to find a new $T$ in which $v_i$ is the root.  I
would like to know what (if any) literature or solutions already
exist for these problems?  I am asking this question because I
am working on a project involving network topologies and would
like to know about any existing solution (especially if they
have proofs) before I start trying to solve the problem on my
own.  share|improve this question  1 Answer 1  up vote 4 down
vote accepted  I think the following paper will probably answer
your first question  Henzinger, M., & Valerie, K. (1997).
Maintaining minimum spanni