Spanning Trees of a Graph

Applied Discrete Structures
by Alan Doerr & Kenneth Levasseur

Graphs play an important role in discrete mathematics. On this page you can explore the set of spanning trees of a graph. Graphs can be created and plotted using Sage. Here we are using the Sage Cell Server. Each cell contains Sage expressions that can be evaluated by clicking on the "Evaluate" button below it. You can edit the contents of the cell to experiment - the original expressions will return when the page reloads.

In the next two cells, the graph g will be the one used in the last two cells. Before evaluating the last cell, you must evaluate the third one, which defines some functions you need.

The simplest way to create a graph is to build a dictionary(or hash function). If you wrap Graph() around a dictionary you get a graph and the plot method can be used to view an embedding of the graph on the plane.

There are many families of graphs included in the graphs package. Here are a few examples, with all but one commented out with #. You can decomment any of them and, optionally, change the parameters to redefine g.

Evaluate the following cell to define functions to generate the tree set of a graph, display the tree sets of a graph, determine whether two trees are adjacent, and draw the adjacency tree graph of a graph. In cells below, these functions are act on whatever graph you defined for the value of g.

Caution: If the graph you define as g is too large, the array of spanning trees and/or the adjacency tree graph probably won't be very informative.

Adjacency tree graph of the selected graph.

Co-trees of the selected graph:

Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial - No Derivative Works 3.0 United States License.