Finding Optimal Spanning Trees For Damaged Networks

We use a representation for the spanning tree where a parent function maps non-root vertices to vertices. Two spanning trees are defined to be adjacent if their function representations differ at exactly one vertex. Given a graph G , we show that the graph H with all spanning trees of G as vertices and any two vertices being adjacent if and only if their parent functions differ at exactly one vertex is connected.