Ask Your Question

Revision history [back]

Use the is_subgraph method.

Using the examples in the question:

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

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

Using Or if the examples in question is up to isomorphism, use the question: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?
sage: G.subgraph_search_count?
sage: G.subgraph_search_iterator?

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.