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 iff their parent functions differ at exactly one vertex is connected.