Number of spanning trees

The spanning trees of the cube C are partitioned into eleven orbits under the action of Isom(C). There are exactly eleven incongruent unfoldings of the cube.

def spanning_trees(G):

   # Helper function to recursively build spanning trees

   def build_tree(H, edges):

       # Check if the subgraph is already connected

       if H.is_connected():

           yield H

       else:

           # Iterate over edges and add them if they don't create cycles

           for i in range(len(edges)):

               if edges[i][1] not in nx.algorithms.descendants(H, edges[i][0]):

                   H1 = H.copy()  # Create a copy of the subgraph

                   H1.add_edge(*edges[i])  # Add the current edge

                   yield from build_tree(H1, edges[i+1:])  # Recursively build the tree with remaining edges

   E = nx.Graph()  # Create an empty graph

   E.add_nodes_from(G)  # Add nodes from the input graph

   return list(build_tree(E, list(G.edges)))  # Return a list of all spanning trees