1 | initial version |

A perfect matching (if the graph has one) is a *spanning elementary subgraph* according your definition. You can get all the perfect matchings (only 1 in your graph) using

```
sage: list(G.perfect_matchings())
[[(7, 10), (1, 2), (11, 12), (3, 4), (5, 6), (8, 9)]]
```

Now if you want all *spanning elementary subgraphs*, you have to design a specific algorithm.

2 | No.2 Revision |

A perfect matching (if the graph has one) is a *spanning elementary subgraph* according your definition. You can get all the perfect matchings (only 1 in your graph) using

```
sage: list(G.perfect_matchings())
[[(7, 10), (1, 2), (11, 12), (3, 4), (5, 6), (8, 9)]]
```

Now if you want all *spanning elementary subgraphs*, you have to design a specific algorithm.

**EDIT:**

A solution is to enumerate all elementary subgraphs and to prune subgraphs without enough vertices.

```
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 {'cycles': [], 'edges': []}, 0
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 sol, n in rec(H, low):
if n >= low:
yield sol, n
# Case 2: select e as an isolated edge
I = H.edges_incident([u, v])
H.delete_vertices([u, v])
for sol, n in rec(H, low - 2):
if n + 2 >= low:
sol['edges'].append((u, v))
yield sol, n + 2
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):
C = [(P[i], P[i + 1]) for i in range(len(P) - 1)]
C.append((u, v))
K = H.copy()
K.delete_vertices(P)
nP = len(P)
for sol, n in rec(K, low - nP):
if n + nP >= low:
sol['cycles'].append(C)
yield sol, n + nP
# Finally restore edge e
H.add_edge(u, v)
for sol, n in rec(G.copy(), nmin):
if n >= nmin:
yield sol
```

The idea behind the algorithm is, given any edge `e=(u,v)`

, to

- either search for solutions without edge
`e`

. We return all elementary subgraphs of`G-e`

. - or
`e`

is in the solution and is a connected component. We remove the end vertices of`e`

from the graph, search for all elementary subgraphs of the remaining graph, and add`e`

to each found subgraph before returning it - or
`e`

is part of a cycle. We enumerate all paths between the end vertices of`e`

. Each path combined with`e`

forms a cycle. For each of these cycles, we search for all elementary subgraphs of the graph`G`

without the vertices of the cycle.

We get the spanning elementary subgraphs as follows:

```
sage: G = Graph([(1,2),(2,3),(3,4),(4,5),(5,1),(6,5),(6,8),(8,9),(7,9),(7,6),(7,10),(10,11),(10,12),(11,12)])
sage: for s in elementary_subgraphs(G, G.order()):
....: print(s)
{'cycles': [], 'edges': [(8, 9), (7, 10), (5, 6), (3, 4), (1, 2), (11, 12)]}
{'cycles': [[(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': [(7, 9), (6, 8)]}
{'cycles': [[(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': [(8, 9), (6, 7)]}
{'cycles': [[(6, 8), (8, 9), (9, 7), (6, 7)], [(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': []}
```

We can also get the elementary subgraphs with at least `G.order() - 1`

vertices:

```
sage: len(list(elementary_subgraphs(G, G.order()-1)))
32
```

or all elementary subgraphs (including the empty graph):

```
sage: len(list(elementary_subgraphs(G, 0)))
647
```

3 | No.3 Revision |

A perfect matching (if the graph has one) is a *spanning elementary subgraph* according your definition. You can get all the perfect matchings (only 1 in your graph) using

```
sage: list(G.perfect_matchings())
[[(7, 10), (1, 2), (11, 12), (3, 4), (5, 6), (8, 9)]]
```

Now if you want all *spanning elementary subgraphs*, you have to design a specific algorithm.

**EDIT:**

A solution is to enumerate all elementary subgraphs and to prune subgraphs without enough vertices.

```
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 {'cycles': [], 'edges': []}, 0
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 sol, n in rec(H, low):
if n >= low:
yield sol, n
# Case 2: select e as an isolated edge
I = H.edges_incident([u, v])
H.delete_vertices([u, v])
for sol, n in rec(H, low - 2):
if n + 2 >= low:
sol['edges'].append((u, v))
yield sol, n + 2
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):
C = [(P[i], P[i + 1]) for i in range(len(P) - 1)]
C.append((u, v))
K = H.copy()
K.delete_vertices(P)
nP = len(P)
for sol, n in rec(K, low - nP):
if n + nP >= low:
sol['cycles'].append(C)
yield sol, n + nP
# Finally restore edge e
H.add_edge(u, v)
for sol, n in rec(G.copy(), nmin):
if n >= nmin:
yield sol
```

The idea behind the algorithm is, given any edge `e=(u,v)`

, to

- either search for solutions without edge
`e`

. We return all elementary subgraphs of`G-e`

. - or
`e`

is in the solution and is a connected component. We remove the end vertices of`e`

from the graph, search for all elementary subgraphs of the remaining graph, and add`e`

to each found subgraph before returning it - or
`e`

is part of a cycle. We enumerate all paths between the end vertices of`e`

. Each path combined with`e`

forms a cycle. For each of these cycles, we search for all elementary subgraphs of the graph`G`

without the vertices of the cycle.

We get the spanning elementary subgraphs as follows:

```
sage: G = Graph([(1,2),(2,3),(3,4),(4,5),(5,1),(6,5),(6,8),(8,9),(7,9),(7,6),(7,10),(10,11),(10,12),(11,12)])
sage: for s in elementary_subgraphs(G, G.order()):
....: print(s)
{'cycles': [], 'edges': [(8, 9), (7, 10), (5, 6), (3, 4), (1, 2), (11, 12)]}
{'cycles': [[(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': [(7, 9), (6, 8)]}
{'cycles': [[(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': [(8, 9), (6, 7)]}
{'cycles': [[(6, 8), (8, 9), (9, 7), (6, 7)], [(1, 5), (5, 4), (4, 3), (3, 2), (1, 2)], [(10, 11), (11, 12), (10, 12)]], 'edges': []}
```

We can also get the elementary subgraphs with at least `G.order() - 1`

vertices:

```
sage: len(list(elementary_subgraphs(G, G.order()-1)))
32
```

or all elementary subgraphs (including the empty graph):

```
sage: len(list(elementary_subgraphs(G, 0)))
647
```

This method is faster for this graph than the (nice) solution using linear programming:

```
sage: %timeit list(spanning_elementary_subgraphs(G))
16.2 s ± 3.41 s per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit list(elementary_subgraphs(G, G.order()))
14.3 ms ± 459 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
```

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.