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.