Generate all spanning trees of a given graph by removing and adding a single edge in each step.
The graph is input as an edge list of the form $u_1,v_1; u_2,v_2; \ldots ; u_m,v_m$.
In such a list, edges are separated by semicolon, vertices are separated by commas, whitespace is ignored, and no double quotes are allowed.
The spanning trees in the output are given as lists of edges, where the edges are numbered $1,2,\ldots,m$, as described in the beginning of the output.
Input graph
Predefined inputs
Output format
Output
numbering
graphics
Object info
The algorithm for this spanning tree Gray code is described as Algorithm S in Knuth's book [Section 7.2.1.6, Knu11].
The implementation running on this website was written by Knuth himself, with some slight modifications for usage within the Combinatorial Object Server.
Such Gray code schemes for spanning trees have been described by several researchers, including Cummins [Cum66], Kamae [Kam67], and Holzmann and Harary [HH72].