If I have an undirected graph G, how could I write a function in Mathematica to obtain a list of subgraphs of G that are isomorphic to some other undirected graph SubG?

I'd like to learn how to program better in Mathematica (unless I explicitly try to prevent it, currently everything I write ends up looking like C code). So please feel free to go heavy on the suggestions of how to approach problems in Mathematica... the "philosophy" of Mathematica programming if you will.

An attempt to show all such graphs is the following:

SubgraphQ[g_,sg_] := Sort[EdgeList[GraphIntersection[g,sg]]]==Sort[EdgeList[sg]]
vertexperm = Thread[#]& /@ 
  ((VertexList[SubG] -> #)& /@ Permutations[VertexList[G],{VertexCount[SubG]}]);
HighlightGraph[G,VertexReplace[SubG,#]]& /@ result

I tested it with the following

{G, SubG} = {PetersenGraph[5,2],EdgeAdd[CycleGraph[5],5<->6]};

and the ideas works. Although since the subgraph has some reordering symmetry (even more obvious if using SubG=CycleGraph[5]), it erroneously gives some identical graphs in the output.

I tried testing it on a 16 vertex graph and a 16 vertex subgraph that I built from hand (and should only have one match), but Mathematica refuses to do the permutations since "it has length at least 13 factorial, which is not a machine integer".

This question is a generalization of the question
Cycles of length N in a graph

Looking around, many of the answers that "look nice" in Mathematica seem to just be "produce the set of all possible answers" and then "prune the set to the correct answers". That sounds like it would take much much more memory, and at least as many (if not more) operations than just the iterating "for loops" type method that pops into my mind from doing procedural programming. Consider for instance sorting a list by using Permutations and then pruning with OrderedQ. Sure it may look short and be conceptually simple, but it is an absolutely horrible way to sort. This is also a good example because the straight forward "for loop" approach (bubble sort) is quick to program, but also not a reasonable algorithm for decent sized lists. In this case Mathematica has a built in Sort. Whenever Mathematica doesn't have a built in solution, I feel like I have to choose between wasting tons of memory or writing lots of code that looks like C but with none of the speed advantages if I had just written it in C.

Even if this is an NP hard problem (I hope it isn't) is there some way to save on memory without resorting to a bunch of "for loops"? Maybe a more intelligent iterator or something? But really what I want is to leverage the abstract capabilities of Mathematica to solve what feels like an inherently mathematical problem. It feels like this should be the correct language to use for these types of problems.

  • 3
    $\begingroup$ You should probably be aware that IsomorphicGraphQ is buggy $\endgroup$
    – Szabolcs
    Mar 9, 2012 at 8:24
  • $\begingroup$ IsomorphicGraphQ is not buggy any more in version 9. $\endgroup$
    – Szabolcs
    May 2, 2013 at 20:48
  • $\begingroup$ Subgraphs are determined by vertex subsets. For a given size you can test each subgraph of that size against your specified graph. This would use the standard IsomorphicGraphQ, hence require no permutations. $\endgroup$ May 2, 2013 at 21:52

2 Answers 2


Update: I now recommend using the IGraph/M package instead of the R interface. It offers the following functions for finding subgraphs:

  • IGSubisomorphicQ tests for subgraph isomorphism, supports multigraphs as well.
  • IGVF2FindSubisomorphisms lists all matching subgraphs found, supports vertex and edge coloured graphs.
  • IGLADFindSubisomorphisms lists all matching subgraphs founds, supports vertex colouring, supports looking only for induced sugraphs.

Daniel is completely correct that this is a hard problem and will usually take a very very long time. However, the igraph library does have a function for it and you can call it through this package. Please read the instructions on how to set up the package, then do this:

{g, subG} = {PetersenGraph[5, 2], EdgeAdd[CycleGraph[5], 5 <-> 6]}

res = IGraph["graph.get.subisomorphisms.vf2"][g, subG];

HighlightGraph[g, Subgraph[g, #]] & /@ Round[res + 1]

enter image description here

Use graph.count.subisomorphisms.vf2 to just count the subgraphs but not retrieve them.

  • $\begingroup$ It seems that graph.get.subisomorphisms.vf2 here returns induced subgraphs in your example. Is it a coincidence? As in the document, only lad method has the option to return induced subgraphs. $\endgroup$
    – hxiao
    Nov 14, 2015 at 7:23
  • $\begingroup$ @HanXiao For this example there is no match which is not an induced subgraph, so yes, it's a coincidence. VF2 does not support searching only for induced subgraphs. BTW consider using IGraphM instead of the R interface. $\endgroup$
    – Szabolcs
    Nov 14, 2015 at 10:32
  • $\begingroup$ Thanks for the quick reply. BTW, I have been waiting for a interface like IGraphM for a long time! $\endgroup$
    – hxiao
    Nov 14, 2015 at 11:09

This is a computationally hard problem. Graph isomorphism is not known to be NP (and also not known to be otherwise). But subgraph isomorphism is, I'm pretty sure, NP-complete. And it looks like that is what you are wanting here.

In contrast, finding cycles is probably not much worse than all-pairs shortest paths. But it will take careful coding. Possibly one might instead use Combinatorica's NumberOfKPaths on each vertex. I do not know how it is implemented, hence cannot comment on efficiency or possible lack thereof.

--- edit --- Finding cycles can be, in worst case, exponentially difficult. For the simple reason that there might be exponentially many. I think the correct claim is that it has complexity something like O(l*n*e+c) where l = cycle length, n = #vertices, e = #edges, and c = #cycles. That's just a guess though. The approach I have in mind could be worse insofar as there could be many candidates that get pruned along the way, that is, as the cycles get built. --- end edit ---

  • $\begingroup$ This is true, but @WideEyed wasn't asking about the efficiency or computational complexity of the problem, even if the problem is NP-complete, it can be solved, just slowly. $\endgroup$
    – tlehman
    Mar 9, 2012 at 18:06
  • $\begingroup$ I know. But my remarks were a bit more than I wanted to put in a comment. Especially as I don't know how to make more than one paragraph without the comment posting itself. $\endgroup$ Mar 9, 2012 at 18:47
  • 2
    $\begingroup$ I think you meant that GI is not known to be NP-complete, as it is known to be in NP. $\endgroup$
    – William
    Mar 10, 2012 at 21:16
  • $\begingroup$ Yes, NP-complete is the unknown for graph isomorphism. Me, I'm betting against it. $\endgroup$ Mar 11, 2012 at 3:53
  • 1
    $\begingroup$ Subgraph isomorphism (the language $\{ \langle G, H \rangle : H \subseteq G \}$ is trivially in NP (witness a set of vertices and a permutation), and is easily seen to be NP-complete by reducing from Clique. $\endgroup$
    – wchargin
    Nov 26, 2017 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.