Spanning elementary subgraphs on a given number of vertices

savecancel

This question has already been (nicely) answered https://ask.sagemath.org/question/435...

I copy here my answer (with small changes to return graphs).

def elementary_subgraphs(G, nmin=0):
    r"""
    Iterator over the elementary subgraphs of `G`.

    A subgraph `H` of a graph `G` is *elementary* if each of its connected
    components is either an edge or a cycle.

    INPUT:

    - ``G`` -- a Graph

    - ``nmin`` -- integer (default: ``0``); lower bound on the number of
      vertices involved in the elementary subgraphs of any returned
      solution. When set to ``G.order()``, the subgraphs must be spanning.
    """
    G._scream_if_not_simple()

    def rec(H, low):
        if not H.size():
            yield Graph()
            return
        if H.order() < low:
            # no solution
            return

        # We select an edge e = (u, v) of H and remove it
        u, v = next(H.edge_iterator(labels=False))
        H.delete_edge((u, v))

        # Case 1: return solutions without e
        for g in rec(H, low):
            if g.order() >= low:
                yield g

        # Case 2: select e as an isolated edge
        I = H.edges_incident([u, v])
        H.delete_vertices([u, v])
        for g in rec(H, low - 2):
            if g.order() + 2 >= low:
                g.add_edge(u, v)
                yield g
        H.add_vertices([u, v])
        H.add_edges(I)

        # Case 3: select e as part of a cycle
        for P in H.all_paths(u, v):
            K = H.copy()
            K.delete_vertices(P)
            nP = len(P)
            for g in rec(K, low - nP):
                if g.order() + nP >= low:
                    g.add_cycle(P)
                    yield g

        # Finally restore edge e
        H.add_edge(u, v)

    yield from rec(G.copy(), nmin)

We can use it like:

sage: G = Graph([(1,2),(2,3),(3,4),(4,5),(5,2),(6,5),(6,7)])
sage: ES = [H for H in elementary_subgraphs(G, nmin=6)]
sage: len(ES)
6