# Spanning elementary subgraphs on a given number of vertices

Consider the following definition:

A subgraph H of a graph $G$ is called an elementary subgraph if each component of $H$ is either an edge or a simple cycle of length at least $3$. A spanning elementary subgraph is a subgraph having all components either edge (edge is a path on two vertices) or simple cycles.

Now my problem is: Consider the following code:

```
G = graphs.EmptyGraph()
G.add_edges([(1, 2), (2, 3), (3, 4), (4, 5), (5, 2), (6, 5), (6, 7)])
G.show()
```

Can we have a Sage code that gives all possible spanning subgraphs on $6$ vertices of the above graph?

Actually I am trying to find the all possible spanning elementary subgraphs on $6$ vertices of the above graph. By $6$ vertices, I mean the subgraphs of order 6 of the original graph.

Should subgraphs be induced?

yes, you are correct

No no, ..there are spanning elementary subgraphs on $6$ vertices. for example, ${(1,2), (3,4),(5,6)}$ is a spanning elementary subgraphs on $6$ vertices. there are many more. another is ${(1,2),(3,4),(6,7)}$. All these spanning elementary subgraphs contains only edge components. There may be cycle components also. for example ${(2,3,4,5),(6,7)}$ is a spanning elementary subgraph on $6$ vertices. I am trying to compute all possible spanning elementary subgraphs on $6$ vertices. Is it clear now? if there is any problem, please let me know.

These subgraphs are not induced.