Let $G$ be a connected graph on $n$ vertices and $\mathcal{T}$ be the set of all spanning trees of $G$.

Consider the graph whose vertices are the elements of $\mathcal{T}$ and

$T, T' \in \mathcal{T}$ are connected by an edge if $|E(T)\cap E(T')| = n - 2 $

Does this graph have a name?

One can see that the graph is connected. Are any of its other properties known?

Is there any literature on this graph?


I have seen this called the Tree Graph of $G$. It has been investigated by a lot of authors. For example Cummings proved in "Hamilton circuits in tree graphs" IEEE Trans. Circuit Theory,13(1966), pp.82-90, that this graph is Hamiltonian. Holzmann and Harary generalized this to tree graphs of matroids in "On the Tree Graph of a Matroid".


Don't know about a name, but for starters see Lovasz "A homology theory for the spanning trees of a graph" http://www.cs.elte.hu/~lovasz/scans/homology-span-tree.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.