# How to check if a graph has a given subgraph?

Consider the Petersen graph G. I want to check if G has a given graph H as an induced subgraph or not. Is it possible to check this? I am new to SageMath.

I wrote this:

G = graphs.PetersenGraph()
H = Graph({1: [2, 3, 4]})


How to check if H is an induced subgraph of G or not?

edit retag close merge delete

Sort by » oldest newest most voted

One could use the is_subgraph method of H, with induced=True.

Or if the question is up to isomorphism, use the search_subgraph method of G.

Define the two graphs:

sage: G = graphs.PetersenGraph()
sage: H = Graph({1: [2, 3, 4]})


Is the small one a subgraph:

sage: H.is_subgraph(G)
False
sage: H.is_subgraph(G, induced=True)
False


Up to isomorphism:

sage: G.subgraph_search(H)
Subgraph of (Petersen graph): Graph on 4 vertices
sage: G.subgraph_search(H, induced=True)
Subgraph of (Petersen graph): Graph on 4 vertices


See the documentation of these methods and related methods:

sage: H.is_subgraph?
sage: G.subgraph_search?


Related methods exist to

• count the number of (induced or not) subgraphs of G isomorphic to H:

sage: G.subgraph_search_count?

• generate all (induced or not) subgraphs of G isomorphic to H:

sage: G.subgraph_search_iterator?


See an example of usage in @David Coudert's comment.

more

Thank you very much for such a detailed answer. Is there any method to find all the induced subgraphs isomorphic to H?

as indicated in above answer, use G.subgraph_search_iterator(H, induced=True).

sage: L = list(G.subgraph_search_iterator(H, induced=True))
sage: len(L)
60
sage: L
[0, 1, 4, 5]
sage: L
[0, 1, 5, 4]


@Captcha it seems you tried to accept the answer but clicked twice, so that the answer was un-accepted.