Using local adaptations to reconfigure a spanning tree of a network (Q1345965)

Let \(G\) be a biconnected graph, let \(S\) be a spanning tree in \(G\), and let \(v\) be a leaf in \(G\), i.e. \(\deg v=1\). A local adaptation \((v, w, x)\) is the event of \(v\) consisting of deleting the link \(vw\) from \(S\) and adding the link \(vx\) to \(S\). Let \(u\) be a vertex in \(G\). The leaf problem is to find a sequence of local adaptations that makes \(u\) a leaf in the spanning tree. It is proved that \(\lceil n/2 \rceil \cdot \lceil n/2-1 \rceil/2\) local adaptions are sufficient to solve any instance of the leaf problem. It is also shown that this bound is tight.