# 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.

edit retag close merge delete

Should subgraphs be induced?

( 2022-02-04 14:11:24 +0200 )edit

yes, you are correct

( 2022-02-04 15:19:07 +0200 )edit

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.

( 2022-02-04 22:00:22 +0200 )edit

These subgraphs are not induced.

( 2022-02-04 22:31:11 +0200 )edit

Sort by » oldest newest most voted

UPD, Solution is modified with respect to the edited question.

Here is a generator of such graphs from a given set of edges:

def add_edges_SES(E,H,i=0):
if i == len(E):
yield H.copy()
return
e = E[i]
if (not H.has_vertex(e[0])) and (not H.has_vertex(e[1])):
H.delete_vertices(e[:2])

def constructSES(G):
C = [frozenset(tuple(sorted(e[:2])) for e in c) for c in G.cycle_basis(output='edge')]
for S in Subsets(C):
T = set()
for c in S:
T = T.symmetric_difference(c)
H = Graph()
if all( H.degree(v) == 2 for v in H.vertices() ):   # only simple cycles allowed


Correspondingly, we can get a list all spanning elementary subgraphs of $G$ on 6 vertices as follows:

SES = [H for H in constructSES(G) if H.order()==6]


It turns out that for a given graph there are 6 such subgraphs on 6 vertices.

more

The code creates a list SES of such subgraphs. Then you can do whatever you want with it. E.g., to show them all run:

for H in SES:
H.show()


or to print their edges run:

for H in SES:
print(H.edges())

( 2022-02-05 13:18:08 +0200 )edit

Actually I am trying to get an answer of the type given in https://ask.sagemath.org/question/435...

( 2022-02-05 15:24:25 +0200 )edit

Actually my question is the following: Find all possible spanning elementary subgraphs on $12$ vertices of the following graph.

G=graphs.EmptyGraph()

G.show()

( 2022-02-06 11:34:24 +0200 )edit

For example $A={ (1,2),(7,6),(3,4),(12,13),(8,9),(10,11) }$ and $B={ (1,2,3,6,7),(8,11,12),(4,5),(9,10) }$ are two spanning elementary subgraphs on $12$ vertices of the given graph $G$. Here $A$ consists only of edges while $B$ contains both edge and cycle components. There are other spanning elementary subgraphs on $12$ vertices of the graph $G$. How to use sagemath to calculate all those spanning elementary subgraphs on $12$ vertices of the graph $G$? Am I clear now?

( 2022-02-06 11:41:17 +0200 )edit

What's wrong with the posted solution?

( 2022-02-06 15:37:51 +0200 )edit

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:
yield g

# 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:
yield g

# Finally restore edge e

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

more