Every connected graph has a spanning tree.
A **spanning tree** *T* of a graph *G* is a tree
that is (a) a subgraph of *G* (i.e., that includes only
edges from *G*) and (b) includes every vertex of *G*.
On the right we show a connected graph and below we show its eight
spanning trees.
Note that the graphs are regarded as being labelled (even though
we don't explicitly show the labels in the list of spanning trees).
The set of labelled trees corresponds to the spanning trees of the
complete graph; the set of free trees correspond to the
unlabelled spanning trees of the complete graph.
Both of these sets of trees may be generated by COS from the
tree generation page.

The **tree graph** of *G*, denoted *T*(*G*), is
the graph whose vertices are the spanning trees of *G* and
whose edges join those spanning trees that differ by an edge
exchange: one edge removed, another added.
Proofs that the tree graph is Hamiltonian may be found in
Cummins (Hamilton circuits in trees graphs,
IEEE Trans. Circuit Theory, CT-13 (1966) 82-90) and
Holzmann and Harary (On the tree graph of a matroid,
SIAM J. Applied Math., 22 (1972) 187-193).

The output of COS is a Hamilton path in *T*(*G*).
Below we show a tree graph of our example graph
and the Hamilton path that is output by COS.

Compare with the actual output of COS shown below. The green edge is the one that just entered the tree; the one above it is the one that left. In the case of Gray Code output, aside from the initial spanning tree, only the entering and leaving edges are shown.

Edges |
Gray Code |
---|---|

1-2, 1-4, 2-3 | 1-2, 1-4, 2-3 |

1-2, 2-4, 2-3 | In: 2-4 Out: 1-4 |

1-2, 2-4, 4-3 | In: 4-3 Out: 2-3 |

1-2, 1-4, 4-3 | In: 1-4 Out: 2-4 |

1-2, 2-3, 4-3 | In: 2-3 Out: 1-4 |

1-4, 2-3, 4-3 | In: 1-4 Out: 1-2 |

1-4, 2-3, 4-2 | In: 4-2 Out: 4-3 |

1-4, 4-3, 4-2 | In: 4-3 Out: 2-3 |

The algorithm we use is due to Malcolm James Smith (Generating Spanning Trees, M.Sc. Thesis, Dept. Computer Science, University of Victoria, 1997).

Determining the number of spanning trees of a graph can be reduced to the problem of computing the determinant of a certain matrix....

**this section yet to be completed!**

It was last updated .